终于遇到一个简单纯粹一点的bfs了......
题目链接:https://www.luogu.org/problemnew/show/P1443
题目是求到达一个点的最短步数 也就是说我只要bfs遍历到这个点的时候顺便给他赋值就好啦 这样肯定是最优解
上代码:
#include<bits/stdc++.h> using namespace std; int sx,sy,n,m,anss[][],ax[]={,,,,-,-,-,-},ay[]={,,-,-,-,-,,};
queue <int> q; void bfs()
{
q.push(sx);
q.push(sy);
q.push();
while(!q.empty())
{
int x=q.front();
q.pop();
int y=q.front();
q.pop();
int k=q.front();
q.pop();
for(int i=;i<;i++)
{
int fx=x+ax[i];
int fy=y+ay[i];
if(fx>=&&fx<=n&&fy>=&&fy<=m&&anss[fx][fy]==-)
{
q.push(fx);
q.push(fy);
q.push(k+);
anss[fx][fy]=k+;
}
}
}
} int main()
{
int i,j;
memset(anss,-,sizeof(anss));
cin>>n>>m>>sx>>sy;
anss[sx][sy]=;
bfs();
for(i=;i<=n;i++)
{
for(j=;j<m;j++)
cout<<left<<setw()<<anss[i][j];
cout<<anss[i][m];
cout<<endl;
}
}
这里我偷懒直接不写结构体了,反正就三个量,挨个压进队列就好了
最后的输出有点坑 第一次没注意提交全WA......
现学了一下c++的左对齐和占五格是怎么实现的(毕竟我菜呀).....