fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define debug(x) cout<<x<<"DE\n";
  6. #define debug2(x,y) cout<<x<<" "<<y<<"DE\n";
  7.  
  8. ll n,m,l1[200][200];
  9. map<pair<ll,ll>,ll>visited;
  10. ll direction2[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
  11.  
  12. bool valid(int a,int b)
  13. {
  14.     if(a>=1&&a<=n&&b>=1&&b<=m)return true;
  15.     else return false;
  16. }
  17.  
  18. ll bfs(ll sx,ll sy)
  19. {
  20.     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)visited[{i,j}]=0;
  21.     queue<pair<ll,ll>>Q;
  22.     Q.push({sx,sy});ll cnt=0;
  23.     visited[{sx,sy}]=1;
  24.     while(!Q.empty()){
  25.         pair<ll,ll>u=Q.front();
  26.         Q.pop();++cnt;
  27.         for(int i=0;i<4;i++){
  28.             ll x=direction2[i][0]+u.first;
  29.             ll y=direction2[i][1]+u.second;
  30.             if(valid(x,y)&&visited[{x,y}]==0){
  31.                 visited[{x,y}]=1;
  32.                 if(l1[x][y]==1){return abs(sx-x)+abs(sy-y);}
  33.                 else Q.push({x,y});
  34.             }
  35.         }
  36.     }
  37.     return 1e18;
  38. }
  39.  
  40. int main()
  41. {
  42.     ll t;
  43.     scanf("%lld",&t);
  44.     while(t--){
  45.         scanf("%lld%lld",&n,&m);
  46.         string s[n+1];
  47.         for(int i=1;i<=n;i++){
  48.             cin>>s[i];
  49.             for(int j=0;j<m;j++){
  50.                 l1[i][j+1]=s[i][j]-'0';
  51.             }
  52.         }
  53.         for(int i=1;i<=n;i++){
  54.             for(int j=1;j<=m;j++){
  55.                 if(l1[i][j]){printf("0 ");}
  56.                 else printf("%lld ",bfs(i,j));
  57.             }cout<<endl;
  58.         }
  59.     }
  60. }
  61.  
Time limit exceeded #stdin #stdout 5s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R9CgVi
language:
C++14 (gcc 8.3)
created:
3 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!