Advertisement
Guest User

Untitled

a guest
Jul 19th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int main() {
  7. int a, b;
  8. scanf("%d %d",&a,&b);
  9. int m[100][100];
  10. int ans[100][100];
  11. vector <vector<bool>> used(100,vector<bool> (100));
  12. for (int i=0;i<a;i++) {
  13. 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; }
  14. }
  15.  
  16. queue <pair<int,int>> q;
  17. pair <int,int> c;
  18. for (int i=0;i<a;i++) {
  19. for (int j=0;j<b;j++) {
  20. if (m[i][j]==1) { used[i][j]=true;
  21. q.push(make_pair(i,j));
  22. used.clear();
  23.  
  24. while (!q.empty()) {
  25. c=q.front();
  26. q.pop();
  27. if ((c.first>=1) && (m[c.first-1][c.second]==0))
  28. { ans[c.first-1][c.second]=min(ans[c.first-1][c.second],ans[c.first][c.second]+1);
  29. if (used[c.first-1][c.second]==false) q.push(make_pair(c.first-1,c.second));
  30. used[c.first-1][c.second]=true;
  31. }
  32.  
  33. if ((c.second>=1) && (m[c.first][c.second-1]==0))
  34. { ans[c.first][c.second-1]=min(ans[c.first][c.second-1],ans[c.first][c.second]+1);
  35. if (used[c.first][c.second-1]==false) q.push(make_pair(c.first,c.second-1));
  36. used[c.first][c.second-1]=true;
  37. }
  38.  
  39. if ((c.second<b-1) && (m[c.first][c.second+1]==0))
  40. { ans[c.first][c.second+1]=min(ans[c.first][c.second+1],ans[c.first][c.second]+1);
  41. if (used[c.first][c.second+1]==false) q.push(make_pair(c.first,c.second+1));
  42. used[c.first][c.second+1]=true;
  43. }
  44.  
  45. if ((c.first<a-1) && (m[c.first+1][c.second]==0))
  46. { ans[c.first+1][c.second]=min(ans[c.first+1][c.second],ans[c.first][c.second]+1);
  47. if (used[c.first+1][c.second]==false) q.push(make_pair(c.first+1,c.second));
  48. used[c.first+1][c.second]=true;
  49. }
  50.  
  51. }
  52. }
  53. }
  54. }
  55.  
  56. for (int w=1;w<10;w++) {
  57. for (int e=1;e<10;e++) cout<<ans[w][e]<<" ";
  58. cout<<"\n";
  59.  
  60. }
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement