BFS 30分求助
查看原帖
BFS 30分求助
439327
南瓜桐楼主2021/12/18 12:36
#include<iostream>
using namespace std;
int n,m,x,y;
struct node{
	int x;
	int y;
}q[160001];
int leftt=1,rightt=1;
int vis[401][401]={},map_step[401][401];
int dx[8] = {-1,1,-1,1,2,2,-2,-2};
int dy[8] = {-2,-2,2,2,-1,1,1,-1};
void bfs(){
	q[rightt].x = x;
	q[rightt].y = y;
	vis[x][y]=1;
	map_step[x][y] = 0;
	while(leftt<=rightt){
		int tx,ty;
		for(int i=0;i<8;i++){
			tx = q[leftt].x + dx[i];
			ty = q[leftt].y + dy[i];
			if(tx>n || tx<1 || ty>m|| ty<1 || vis[tx][ty]==1)continue;
			++rightt;
			q[rightt].x = tx;
			q[rightt].y = ty;
			vis[tx][ty] = 1;
			map_step[tx][ty] = map_step[ q[leftt].x ][ q[leftt].y ] + 1;
		
		}
		++leftt;
	}
	return;
}
int main(){
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			map_step[i][j]=-1;
			vis[i][j]=0;
		}
	}
	bfs();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(map_step[i][j]==-1){
				cout<<"-1   ";
			}else{
				cout<<map_step[i][j]<<"    ";
			}
		}
		cout<<endl;
	}
	return 0;
} 
/*
输入只有一行四个整数,分别为 n, m, x, y。
0    3    2    
3    -1   1    
2    1    4    
*/
2021/12/18 12:36
加载中...