BFS算法

题目

解题思路

代码

#include <iostream> #include <queue> #include <cstring> using namespace std; typedef pair<int,int> PII; const int N=410; int n,m,x,y; int dist[N][N]; // 骑士8个移动方向 int dx[]={1,2,2,1,-1,-2,-2,-1}; int dy[]={2,1,-1,-2,-2,-1,1,2}; void bfs() { memset(dist,-1,sizeof(dist)); // 初始化距离为-1 queue<PII> q; q.push({x,y}); dist[x][y]=0; // 起点距离为0 while(q.size()) { auto t=q.front(); q.pop(); int i=t.first,j=t.second; for(int k=0;k<8;k++) { int nx=i+dx[k],ny=j+dy[k]; // 检查是否在棋盘范围内，且未被访问过 if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dist[nx][ny]==-1) { dist[nx][ny]=dist[i][j]+1; // 更新距离 q.push({nx,ny}); } } } } int main() { cin>>n>>m>>x>>y; bfs(); // 按行列输出，每行对应棋盘的一行 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<dist[i][j]<<" "; } cout<<endl; } return 0; }