fork(9) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<string>
  5. using namespace std;
  6.  
  7. int scan[185][185];
  8. int ans[185][185];
  9. int nx[185];
  10. int ny[185];
  11. int N,M,test;
  12. //computing distance
  13.  int dis(int i,int j,int k ,int l){
  14.         int one=i-k;
  15.         int two=j-l;
  16.         if (one<0)one*=-1;
  17.         if (two<0)two*=-1;
  18.         return one+two;
  19.     }
  20.  
  21.  
  22. //my dfs function 
  23. void dfs(int n,int m,int i,int j){
  24.         if(i>=0&&i<N&&j>=0&&j<M){
  25.         if (scan[i][j]==1)return;
  26.         int d=dis(n,m,i,j);
  27.         if(ans[i][j]<=d)return;
  28.         ans[i][j]=d;
  29.         dfs(n,m,i,j+1);
  30.         dfs(n,m,i,j-1);
  31.         dfs(n,m,i-1,j);
  32.         dfs(n,m,i+1,j);
  33. 	}
  34. 	else return;
  35. }
  36.  
  37.  
  38.  
  39. int main(){
  40.  
  41.       int n;
  42.       string s;
  43.                 //getting number of testcase
  44.       scanf("%d",&test);
  45.        for(int t=0;t<test;t++){
  46.            n=0;
  47.                         //getting row and column
  48.            scanf("%d %d",&N,&M);
  49.            for(int i=0;i<N;i++)
  50.                 for(int j=0;j<M;j++)ans[i][j]=32000;
  51.  
  52.                         //getting input
  53.            for(int i=0;i<N;i++){
  54.                cin>>s;
  55.                for(int j=0;j<M;j++){   
  56.                    scan[i][j]=s[j]-'0';
  57.                    if(scan[i][j]==1){
  58.                             nx[n]=i;ny[n]=j;
  59.                             n++;
  60.                    }                                     
  61.                }
  62.            }
  63.            //starts searching
  64.            for(int i=0;i<n;i++){
  65.                ans[nx[i]][ny[i]]=0;
  66.                dfs(nx[i],ny[i],nx[i],ny[i]+1);
  67.                dfs(nx[i],ny[i],nx[i],ny[i]-1);
  68.                dfs(nx[i],ny[i],nx[i]+1,ny[i]);
  69.                dfs(nx[i],ny[i],nx[i]-1,ny[i]);
  70.            }
  71.  
  72.            //printing
  73.            for(int i=0;i<N;i++){
  74.                for(int j=0;j<M;j++){
  75.                    printf("%d ",ans[i][j]);
  76.                 } 
  77.                printf("\n");
  78.            }
  79.  
  80.        }
  81.         return 0;
  82. }
  83.  
  84.  
  85.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2p8VC
language:
Java (HotSpot 12)
created:
13 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!