luogu P1443 马的遍历(BFS

BFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define MAXN 100005
#define MAXM 1000005
int n,m,X,Y;
int dx[10]={0,1,2,-2,-1,-1,2,1,-2};
int dy[10]={0,2,1,-1,-2,2,-1,-2,1};
queue<int>qx,qy,qstep;
int mp[410][410];
bool book[410][410];
void bfs(){
	int x,y,step;
	while(!qx.empty()){
		x=qx.front();
		y=qy.front();
		step=qstep.front();
		mp[x][y]=step;
		qx.pop(),qy.pop(),qstep.pop();
		for(int i=1;i<=8;i++){
			if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&book[x+dx[i]][y+dy[i]]==0){//n m
				book[x+dx[i]][y+dy[i]]=1;
				qx.push(x+dx[i]);
				qy.push(y+dy[i]);
				qstep.push(step+1);
			}
		}
	}
}
int main(){
	cin>>n>>m>>X>>Y;
	qx.push(X);qy.push(Y);
	qstep.push(0);
	book[X][Y]=1;
	bfs();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){// m n
			if(book[i][j]==0)cout<<"-1   ";
			else {
				printf("%-5d",mp[i][j]);
			}
			
		}printf("\n");
	}
	
    return 0;
}


上一篇:【Swift Mac开发】自定义NSTableView选中行背景


下一篇:Qt通用方法及类库12