fork(1) download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<climits>
  4. #include<queue>
  5. #include<utility>
  6.  
  7. using namespace std;
  8.  
  9. void bfs(queue<pair<int,int> >& bfsQue, int (&dist)[182][182],bool (&color)[182][182], int n, int m) {
  10.   pair<int,int> temp;
  11.   int x,y;
  12.   while(!bfsQue.empty()) {
  13.     x=bfsQue.front().first;
  14.     y=bfsQue.front().second;
  15.     bfsQue.pop();
  16.     if((x+1<m)&&(color[x+1][y]==1)) {
  17.       temp.first=x+1;
  18.       temp.second=y;
  19.       bfsQue.push(temp);
  20.       color[x+1][y]=0;
  21.       dist[x+1][y]=dist[x][y]+1;
  22.     }
  23.  
  24.     if((x-1>=0)&&(color[x-1][y]==1)) {
  25.       temp.first=x-1;
  26.       temp.second=y;
  27.       bfsQue.push(temp);
  28.       color[x-1][y]=0;
  29.       dist[x-1][y]=dist[x][y]+1;
  30.     }
  31.  
  32.     if((y+1<m)&&(color[x][y+1]==1)) {
  33.       temp.first=x;
  34.       temp.second=y+1;
  35.       bfsQue.push(temp);
  36.       color[x][y+1]=0;
  37.       dist[x][y+1]=dist[x][y]+1;
  38.     }
  39.  
  40.     if((y-1>=0)&&(color[x][y-1]==1)) {
  41.       temp.first=x;
  42.       temp.second=y-1;
  43.       bfsQue.push(temp);
  44.       color[x][y-1]=0;
  45.       dist[x][y-1]=dist[x][y]+1;       
  46.     }
  47.   }
  48. }
  49.  
  50. int main() {
  51.   int n,m,nTest,sz;
  52.   char ch,str[183];
  53.   int dist[182][182];
  54.   bool color[182][182];
  55.  
  56.   pair<int,int> temp;
  57.   queue<pair<int,int> > bfsQue;
  58.  
  59.   scanf("%d",&nTest);
  60.  
  61.   for(int i=0;i<nTest;i++) {
  62.     scanf("%d%d",&n,&m);
  63.  
  64.     for(int j=0;j<n;j++) {
  65.       scanf("%s",str);
  66.  
  67.  
  68.       for(int k=0;k<m;k++) {	
  69. 	ch=str[k]-48;
  70. 	if(!ch) {
  71. 	  dist[j][k]=INT_MAX;
  72. 	  color[j][k]=1;
  73. 	}
  74. 	else {
  75. 	  dist[j][k]=0;
  76. 	  color[j][k]=0;
  77. 	  temp.first=j;
  78. 	  temp.second=k;
  79. 	  bfsQue.push(temp);
  80. 	}
  81.       }
  82.  
  83.  
  84.     }
  85.  
  86.     bfs(bfsQue,dist,color,n,m);
  87.  
  88.     for(int j=0;j<n;j++) {
  89.       for(int k=0;k<m;k++) {
  90. 	printf("%d",dist[j][k]);
  91. 	if(k!=(m-1))
  92. 	  printf(" ");
  93.       }
  94.       printf("\n");
  95.     }
  96.  
  97.   }
  98.   return 0;
  99. }
  100.  
  101.  
Success #stdin #stdout 0s 2908KB
comments (?)
stdin
copy 
1
3 4
0001
0011
0110
stdout
copy 
3 2 1 0
2 1 0 0
1 0 0 1
https://ideone.com/ffBWcn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!