fork(2) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int dis[190][190];
  5. bool visit[190][190];
  6. void bfs(pair<int,int> p)
  7. {
  8.     int fixi=p.first;
  9.     int fixj=p.second;
  10.     memset(visit,false,sizeof(visit));
  11.     queue<pair<int,int> >q;
  12.     q.push(p);
  13.     visit[fixi][fixj]=true;
  14.     while(!q.empty())
  15.     {
  16.         int i=q.front().first;
  17.         int j=q.front().second;
  18.         q.pop();
  19.         dis[i][j]=min(dis[i][j],abs(i-fixi)+abs(j-fixj));
  20.  
  21.         if(i>0 && !visit[i-1][j])
  22.         {
  23.             q.push(make_pair(i-1,j));
  24.             visit[i-1][j]=true;
  25.         }
  26.  
  27.         if(j>0 && !visit[i][j-1])
  28.         {
  29.             visit[i][j-1]=true;
  30.             q.push(make_pair(i,j-1));
  31.         }
  32.  
  33.         if(i<n-1 && !visit[i+1][j])
  34.         {
  35.             q.push(make_pair(i+1,j));
  36.             visit[i+1][j]=true;
  37.         }
  38.  
  39.         if(j<m-1 && !visit[i][j+1])
  40.         {
  41.             visit[i][j+1]=true;
  42.             q.push(make_pair(i,j+1));
  43.         }
  44.     }
  45. }
  46. int main()
  47. {
  48.     std::ios::sync_with_stdio(false);
  49.     int t;
  50.     cin>>t;
  51.     while(t--)
  52.     {
  53.         queue<pair<int,int> > q1s;
  54.         cin>>n>>m;
  55.  
  56.         memset(dis,10000,sizeof(dis));
  57.         for(int i=0;i<n;i++)
  58.             {
  59.                 string s;
  60.                 cin>>s;
  61.                 for(int j=0;j<m;j++)
  62.                 {
  63.                     if(s[j]=='1')
  64.                     {
  65.                         q1s.push(make_pair(i,j));
  66.                         dis[i][j]=0;
  67.                     }
  68.                 }
  69.             }
  70.  
  71.         while(!q1s.empty())
  72.         {
  73.             bfs(q1s.front());
  74.             q1s.pop();
  75.         }
  76.  
  77.         for(int i=0;i<n;i++)
  78.         {
  79.             for(int j=0;j<m;j++)
  80.             cout<<dis[i][j]<<" "; //One thing I have figured out is that when I try to print dis for values of
  81.             cout<<"\n";           //i,j larger than n and m it shows some values instead of 0
  82.         }                         //i.e dis table is being filled even for values of i,j greater than n,m
  83.     }
  84.  
  85. }
  86. /*
  87. 1
  88. 3 4
  89. 0001
  90. 0011
  91. 0110
  92. */
  93.  
Success #stdin #stdout 0s 3632KB
comments (?)
stdin 
1
3 4
0001
0011
0110
stdout 
3 2 1 0 
2 1 0 0 
1 0 0 1
https://ideone.com/ppgQiW
language:
C++14 (gcc 8.3)
created:
8 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!