Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- int main() {
- int a, b;
- scanf("%d %d",&a,&b);
- int m[100][100];
- int ans[100][100];
- vector <vector<bool>> used(100,vector<bool> (100));
- for (int i=0;i<a;i++) {
- for (int j=0;j<b;j++) { scanf("%d",&m[i][j]); if (m[i][j]==1) ans[i][j]=0; else ans[i][j]=100000; used[i][j]=false; }
- }
- queue <pair<int,int>> q;
- pair <int,int> c;
- for (int i=0;i<a;i++) {
- for (int j=0;j<b;j++) {
- if (m[i][j]==1) { used[i][j]=true;
- q.push(make_pair(i,j));
- used.clear();
- while (!q.empty()) {
- c=q.front();
- q.pop();
- if ((c.first>=1) && (m[c.first-1][c.second]==0))
- { ans[c.first-1][c.second]=min(ans[c.first-1][c.second],ans[c.first][c.second]+1);
- if (used[c.first-1][c.second]==false) q.push(make_pair(c.first-1,c.second));
- used[c.first-1][c.second]=true;
- }
- if ((c.second>=1) && (m[c.first][c.second-1]==0))
- { ans[c.first][c.second-1]=min(ans[c.first][c.second-1],ans[c.first][c.second]+1);
- if (used[c.first][c.second-1]==false) q.push(make_pair(c.first,c.second-1));
- used[c.first][c.second-1]=true;
- }
- if ((c.second<b-1) && (m[c.first][c.second+1]==0))
- { ans[c.first][c.second+1]=min(ans[c.first][c.second+1],ans[c.first][c.second]+1);
- if (used[c.first][c.second+1]==false) q.push(make_pair(c.first,c.second+1));
- used[c.first][c.second+1]=true;
- }
- if ((c.first<a-1) && (m[c.first+1][c.second]==0))
- { ans[c.first+1][c.second]=min(ans[c.first+1][c.second],ans[c.first][c.second]+1);
- if (used[c.first+1][c.second]==false) q.push(make_pair(c.first+1,c.second));
- used[c.first+1][c.second]=true;
- }
- }
- }
- }
- }
- for (int w=1;w<10;w++) {
- for (int e=1;e<10;e++) cout<<ans[w][e]<<" ";
- cout<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement