广搜bfs-P1443 马的遍历

P1443 马的遍历

题目来源-洛谷

题意

要求马到达棋盘上任意一个点最少要走几步

思路

• 国际棋盘规则是马的走法是-日字形，也称走马日，即x,y一个是走两步，一个是一步

• 要求最小步数，所以考虑第一次遍历到的点即为最小步数，即bfs宽搜处理

• 套模板，遍历的可能即为当前位置的不同走法，借助数组来处理

  int zx[] = {1,1,-1,-1,2,2,-2,-2} ; int zy[] = {2,-2,2,-2,1,-1,1,-1};坐标入队时即刻更新步数即可

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 405;
void bfs(int x,int y);
int m,n;//n行m列
struct node{
	int x,y;
};
queue <node> q;
int zx[] = {1,1,-1,-1,2,2,-2,-2} ;
int zy[] = {2,-2,2,-2,1,-1,1,-1};
bool f[MAXN][MAXN] = {false};
int ans[MAXN][MAXN] ;
int main(){
	int x0,y0; 
	cin>>n>>m>>x0>>y0;
	bfs(x0,y0) ;
	return 0;
}
void bfs(int x,int y){
	//node k = (x,y);//直接创建一个结构体 -这种建法需要做自定义函数 
	node k = node{x,y} ;
	q.push(k);
	f[x][y] = true;
	while(!q.empty()){
		int x1 = q.front().x,y1 = q.front().y ;//取出队首 
		q.pop();//弹出队首 
		for(int i=0;i<8;i++){
			int nx = x1+zx[i],ny = y1+zy[i];//忘八个方向遍历 
			if(nx<1||nx>n||ny<1||ny>m||f[nx][ny]) continue;//越界或者被访问过则访问下一个点
			q.push((node){nx,ny});//该点入队 
			ans[nx][ny] = ans[x1][y1]+1 ; //该点一定是马从（x1,y1）点走过来的 
			f[nx][ny] = true;//标记 
		}
	}
	//输出答案
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j] ) cout<<ans[i][j]<<" ";
			else cout<<-1<<" ";//没被访问过说明没办法走到，-1 
		}
		cout<<endl;
	} 
	return ;
}