fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl cout<<"\n";
  3. #define fi first
  4. #define int long long
  5. #define se second
  6. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  7. #define op freopen
  8. #define TXT "test"
  9. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  10.  
  11. using namespace std;
  12. int n,m,d1[1005][1005],d2[1005][1005];
  13. bool vs1[1005][1005],vs2[1005][1005];
  14. bool x[1005][1005];
  15. vector<pair<int,int>> a[1005][1005];
  16. void bfs(pair<int,int> i, int d[1005][1005] , bool vs[1005][1005] )
  17. {
  18.     queue<pair<int,int>> q;
  19.     pair<int,int> c;
  20.     q.push(i);
  21.     vs[i.fi][i.se]=1;
  22.     while(!q.empty())
  23.     {
  24.         c=q.front();
  25.         q.pop();
  26.         for(pair<int,int> &j:a[c.fi][c.se])
  27.         {
  28.             if(!vs[j.fi][j.se])
  29.             {
  30.                 d[j.fi][j.se]=d[c.fi][c.se]+1;
  31.                 vs[j.fi][j.se]=1;
  32.                 q.push(j);
  33.             }
  34.         }
  35.     }
  36. }
  37. main()
  38. {
  39.     ios;
  40.     freo;
  41.     cin>>n>>m;
  42.     for(int i=1;i<=n;i++)
  43.     {
  44.         for(int j=1;j<=m;j++)
  45.         {
  46.             cin>>x[i][j];
  47.         }
  48.     }
  49.     for(int i=1;i<=n;i++)
  50.     {
  51.         for(int j=1;j<=m;j++)
  52.         {
  53.             if(!x[i][j]&&!x[i][j+1])
  54.             {
  55.                 a[i][j].push_back({i,j+1});
  56.                 a[i][j+1].push_back({i,j});
  57.             }
  58.             if(!x[i][j]&&!x[i+1][j])
  59.             {
  60.                 a[i][j].push_back({i+1,j});
  61.                 a[i+1][j].push_back({i,j});
  62.             }
  63.             if(!x[i][j]&&!x[i][j-1])
  64.             {
  65.                 a[i][j].push_back({i,j-1});
  66.                 a[i][j-1].push_back({i,j});
  67.             }
  68.             if(!x[i][j]&&!x[i-1][j])
  69.             {
  70.                 a[i][j].push_back({i-1,j});
  71.                 a[i-1][j].push_back({i,j});
  72.             }
  73.         }
  74.     }
  75.     bfs({1,1},d1,vs1);
  76.     bfs({n,m},d2,vs2);
  77.     int MIN=INT_MAX;
  78.     bool OK=0;
  79.     for(int i=1;i<=n;i++)
  80.     {
  81.         for(int j=1;j<=m;j++)
  82.         {
  83.             if(vs1[i][j]&&vs2[i][j]&&d1[i][j]==d2[i][j])
  84.             {
  85.                 MIN=min(MIN,d1[i][j]);
  86.                 OK=1;
  87.             }
  88.         }
  89.     }
  90.     if(!OK)
  91.         cout<<"#";
  92.     else
  93.         cout<<MIN;
  94. }
  95.  
Success #stdin #stdout 0.01s 30976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#
https://ideone.com/yke9TS
language:
C++ (gcc 8.3)
created:
12 days 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!