1 solutions
-
0
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define x first #define y second int n,m; const int N=1010; int dist[N][N]; char g[N][N]; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; void bfs() { queue<PII> q; memset(dist,0x3f,sizeof dist); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='1') { q.push({i,j}); dist[i][j]=0; } } } while(q.size()) { PII t=q.front(); q.pop(); for(int i=0;i<4;i++) { int a=t.x+dx[i],b=t.y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue; if(g[a][b]=='1') continue; if(dist[a][b]!=0x3f3f3f3f) continue; dist[a][b]=dist[t.x][t.y]+1; q.push({a,b}); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>g[i]; } bfs(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cout<<dist[i][j]<<" "; } cout<<endl; } return 0; }
- 1
Information
- ID
- 228
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 26
- Accepted
- 7
- Uploaded By