bfs 30 求调
查看原帖
bfs 30 求调
807584
mengqifeng楼主2024/11/20 22:12
#include <iostream>
#include <queue>
using namespace std;
int n,m;
char pic[185][185];
int ans[185][185];
bool vis[105][105];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node
{
	int x,y,d;
};
queue<node>que;
void PRINT()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<pic[i][j];
		cout<<endl;
	}
}
void bfs()
{
	while(!que.empty())
	{
		node tmp=que.front();
		que.pop();
		ans[tmp.x][tmp.y]=min(tmp.d,ans[tmp.x][tmp.y]);
		for(int i=0;i<4;i++)
		{
			int xx=tmp.x+dx[i],yy=tmp.y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy])continue;
			vis[xx][yy]=1;
			que.push({xx,yy,ans[tmp.x][tmp.y]+1});
			
		}
	}
}
int main()
{
	char x;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>pic[i][j];
			if(pic[i][j]=='1')
			{	
				que.push({i,j,0});
				vis[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(pic[i][j]!='1')ans[i][j]=1e7;
	//PRINT();
	bfs();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<ans[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}
2024/11/20 22:12
加载中...