fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char a[185][185];
  4. int dp[185][185],visited[185][185];
  5. int h,w;
  6. int dx[] = {1,1,0,-1,-1,-1,0,1};
  7. int dy[] = {0,-1,-1,-1,0,1,1,1};
  8. void dfs(int x,int y)
  9. {
  10.     if(a[x][y]=='1')
  11.     {
  12.         dp[x][y]=0;
  13.         return;
  14.     }
  15.  
  16.     int temp1,temp2;
  17.     visited[x][y]=1;
  18.  
  19.     for(int k=0;k<8;k++)
  20.     {
  21.         int nx = x + dx[k];
  22.         int ny = y + dy[k];
  23.  
  24.         if(nx>=0&&ny>=0&&nx<h&&ny<w)
  25.         {
  26.  
  27.         	temp1 = dx[k];
  28.         	temp2 = dy[k];
  29.         	if(temp1<0)temp1=(temp1)*(-1);
  30.         	if(temp2<0)temp2=(temp2)*(-1);
  31.  
  32.             if(visited[nx][ny]==0)
  33.             dfs(nx,ny);
  34.             dp[x][y] = min(dp[x][y],dp[nx][ny]+temp1+temp2);
  35.         }
  36.     }
  37.     visited[x][y]=0;
  38. }
  39. int main()
  40. {
  41.     int t;
  42.     cin>>t;
  43.     while(t--)
  44.     {
  45.         cin>>h>>w;
  46.  
  47.         for(int i=0;i<h;i++)
  48.         cin>>a[i];
  49.         memset(visited,0,sizeof(visited));
  50.  
  51.         for(int i=0;i<h;i++)
  52.         for(int j=0;j<w;j++)
  53.         dp[i][j]=100000;
  54.  
  55.         for(int i=0;i<h;i++)
  56.         {
  57.             for(int j=0;j<w;j++)
  58.             {
  59.                 if(dp[i][j]==100000&&a[i][j]!='1')
  60.                 dfs(i,j);
  61.             }
  62.         }
  63.         for(int i=0;i<h;i++)
  64.         {
  65.             if(i!=0)
  66.             cout<<"\n";
  67.             for(int j=0;j<w;j++)
  68.             {
  69.               if(a[i][j]=='1')
  70.               cout<<"0 ";
  71.               else
  72.               cout<<dp[i][j]<<" ";
  73.             }
  74.  
  75.         }
  76.         cout<<"\n";
  77.     }
  78.     return 0;
  79. }
  80.  
  81.  
Success #stdin #stdout 0s 3600KB
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/kRwW8I
language:
C++ (gcc 8.3)
created:
9 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!