广度优先搜索题解

点个赞吧！

#include<bits/stdc++.h>
using namespace std;
int a,b;
int x1,y1;
int n[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
int maps[500][500];
struct dd1{
	int x,y,sum;
};
void bfs(){
	queue<dd1>q;
	q.push({x1,y1,0});
	maps[x1][y1]=0;
	while(!q.empty()){
		int nx=q.front().x;
		int ny=q.front().y;
		int sum=q.front().sum;
		q.pop();
		for(int i=0;i<8;i++){
			int tx=nx+n[i][0];
			int ty=ny+n[i][1];
			if(tx<1||ty<1||tx>a||ty>b) continue;
			if(maps[tx][ty]!=-1) continue;
			maps[tx][ty]=sum+1;
			q.push({tx,ty,sum+1});
		}
	}
}
int main(){
	cin>>a>>b>>x1>>y1;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			maps[i][j]=-1;
		}
	}
	bfs();
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			cout<<maps[i][j]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

有注释：

#include<bits/stdc++.h>
using namespace std;
const int N=500;

int n,m,x,y;
int mp[N][N];
struct node{
	int x,y,sum;
};

//      上偏左   上偏右   右偏上  右偏下  下偏右  下偏左   左偏下   左偏上 
int dx[]={-2,      -2,     -1,      1,      2,      2,       1,       -1};//方向数组 
int dy[]={-1,      1,      2,       2,      1,     -1,      -2,       -2};//方向数组 

void bfs(int x,int y){
	queue<node>q;//维护 
	q.push({x,y,0});
	while(q.size()>0){
		int nx=q.front().x;//维护 
		int ny=q.front().y;//维护 
		int sum=q.front().sum;//维护 
		q.pop();
		for(int i=0;i<8;i++){
			int tx=nx+dx[i];
			int ty=ny+dy[i];
			if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&mp[tx][ty]==-1){
				mp[tx][ty]=sum+1;
				q.push({tx,ty,sum+1});
			}
		}
	}
}

int main(){
	//输入：
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mp[i][j]=-1;
		}
	}
	//处理：
	mp[x][y]=0;
	bfs(x,y);
	
	//输出：
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<mp[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}