开了氧气还是70分
查看原帖
开了氧气还是70分
788156
a2528904238楼主2023/3/2 14:15
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
vector<PII> v;
LL f[220][220];
LL a[220][220];
int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
int n,m;
bool st[220][220];
void bfs(int x,int y)
{
	memset(st,false,sizeof st);
	queue<PII> q;
	q.push({x,y});
	st[x][y] = true;
	while(!q.empty())
	{
		PII t = q.front();
		q.pop();
		for(int i = 0 ; i < 4 ; i ++)
		{
			int nx = t.first+dx[i],ny=t.second+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!st[nx][ny])
			{
				f[nx][ny] = min(f[t.first][t.second]+1,f[nx][ny]);
				q.push({nx,ny});
				st[nx][ny] = true;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(f,0x3f,sizeof f);
	string s;
	for(int i = 1 ; i <= n ; i ++)
	{
		cin>>s;
		s = " "+s;
		for(int j = 1 ; j <= m ; j ++)
		{
			a[i][j]=s[j]-'0';
			if(a[i][j]==1) 
			{
				f[i][j] = 0;
				v.push_back({i,j});
			}
		}
	}
	for(int i = 0 ; i < v.size() ; i ++)
	{
		PII t =v[i];
		bfs(t.first,t.second);
	}
	for(int i = 1 ; i <= n ; i ++)
	{
			for(int j = 1 ; j <= m ; j ++)
		{
			cout<<f[i][j]<<' ';
		}
		cout<<endl;
	}
}  

2023/3/2 14:15
加载中...