fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define se second
  4. #define fi first
  5. #define fo(i,m,n) for(int i=m;i<n;i++)
  6. #define ll long long
  7. #define l long
  8. #define vecll vector<ll>
  9. #define vecl vector<l>
  10. #define veci vector<int>
  11. #define mp make_pair
  12. #define bg begin()
  13. #define ed end()
  14. #define ios ios_base::sync_with_stdio(0)
  15. #define pb push_back
  16. #define xd LLONG_MAX
  17. #define inf 1000000
  18. int a[1001][1001];
  19. char c[1001][1001];
  20. int vis[1001][1001];
  21. int n,m;
  22. void BFS(int x,int y,int k)
  23. {
  24. vis[x][y]=1;  // marked node as visited
  25.  
  26. queue<pair<pair<int,int>,int>> q;  
  27. q.push(mp(mp(x,y),k));     // pair ((vertices),time)
  28. while(!q.empty())
  29. {
  30. int f=q.front().fi.fi;         // x coordinate
  31. int g=q.front().fi.se;       // y coordinate
  32. int h=q.front().se;           // time associated
  33. h=max(a[f][g],h);            // may be the itself have some more value than previous cycle
  34. q.pop();
  35. if(a[f][g-1]!=-1&&h>0&&g-1>=0&&vis[f][g-1]==0)  // if a[val]!=-1 and time>0  and in array and not visited
  36. {vis[f][g-1]=1;                              // mark as visited
  37. //c[f][g-1]='Y';
  38. q.push(mp(mp(f,g-1),h-1));             // push vertices and time left with them
  39. }	
  40.  
  41.  
  42. if(a[f][g+1]!=-1&&h>0&&g+1<m&&vis[f][g+1]==0)
  43. {vis[f][g+1]=1;
  44. //c[f][g+1]='Y';
  45. q.push(mp(mp(f,g+1),h-1));
  46. }
  47.  
  48. if(a[f-1][g]!=-1&&h>0&&f-1>=0&&vis[f-1][g]==0)
  49. {vis[f-1][g]=1;
  50. //c[f-1][g]='Y';
  51. q.push(mp(mp(f-1,g),h-1));
  52. }
  53.  
  54. if(a[f+1][g]!=-1&&h>0&&f+1<n&&vis[f+1][g]==0)
  55. {vis[f+1][g]=1;
  56. //c[f+1][g]='Y';
  57. q.push(mp(mp(f+1,g),h-1));
  58. }
  59. }// While
  60.  
  61. } // BFS
  62. int main()
  63. {ios;
  64. cin.tie(NULL);	
  65. int t;
  66. cin>>t;            // test cASES
  67. while(t--)
  68. {
  69. priority_queue<pair<int,pair<int,int>>> pr;   //priority queue for greater element at front
  70. cin>>n>>m;         // rows columns
  71. fo(i,0,n)      // 0 to n-1
  72. fo(j,0,m)
  73. {
  74. cin>>a[i][j];       // insert array value
  75. vis[i][j]=0;        // univisit 
  76. if(a[i][j]>0)
  77. pr.push(mp(a[i][j],mp(i,j)));    // inserting time values in priority queue
  78. }
  79. while(!pr.empty())
  80. {
  81. int x=pr.top().se.fi;   // x coordinate for BFS
  82. int y=pr.top().se.se;  // y coordinate for BFS
  83. int k=pr.top().fi;    // associated time with vertex for BFS
  84. pr.pop();
  85. if(vis[x][y]==0)        // run only if it is not visited
  86. BFS(x,y,k);
  87. }
  88. fo(i,0,n)
  89. {fo(j,0,m)
  90. {
  91. if(vis[i][j]==1)        // if array was visited then Y
  92. cout<<"Y";
  93. else if(a[i][j]==-1) 
  94. cout<<"B";
  95. else cout<<"N";
  96. }
  97. cout<<"\n";
  98. }
  99.  
  100. }
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111. 	return 0;
  112. }
Success #stdin #stdout 0s 24872KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OLCxhx
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!