fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define pill pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ff fi.fi
  12. #define fs fi.se
  13. #define sf se.fi
  14. #define ss se.se
  15. #define MASK(x) (((1)<<(x))-1)
  16. #define getbit(x,k) (((x)>>(k))&1)
  17.  
  18. using namespace std;
  19.  
  20. const int maxn=1e3+5,mod=1e9+7;
  21. const ll inf=1e18;
  22.  
  23. int n,m;
  24. int dx[]={0,0,-1,1,-1,-1,1,1},dy[]={1,-1,0,0,-1,1,-1,1};
  25. int ans;
  26. void bfs(vector<vector<char>>A, vector<vector<int>>d)
  27. {
  28.     deque<pair<int,pii>>dQ;
  29.     for(int i=1;i<=n;i++) if(A[i][1]!='@')
  30.     {
  31.         d[i][1]=(A[i][1]=='.');
  32.         if(d[i][1]) dQ.push_back({1,{i,1}});
  33.         else dQ.push_front({0,{i,1}});
  34.     }
  35.     for(int i=1;i<=m;i++) if(A[n][i]!='@')
  36.     {
  37.         d[n][i]=(A[n][i]=='.');
  38.         if(d[n][i]) dQ.push_back({1,{n,i}});
  39.         else dQ.push_front({0,{n,i}});
  40.     }
  41.     while(dQ.size())
  42.     {
  43.         pair<int,pii> u=dQ.front();dQ.pop_front();
  44.         if(u.fi!=d[u.sf][u.ss]) continue;
  45.         int x=u.sf,y=u.ss;
  46.         if(x==1 || y==m) ans=min(ans,u.fi);
  47.         for(int k=0;k<8;k++)
  48.         {
  49.             int nx=x+dx[k],ny=y+dy[k],c=1;
  50.             if(nx<1 || nx>n || ny<1 || ny>m) continue;
  51.             if(A[nx][ny]=='@') continue;
  52.             if(A[nx][ny]=='#') c=0;
  53.             if(d[nx][ny]>u.fi+c)
  54.             {
  55.                 d[nx][ny]=u.fi+c;
  56.                 if(c==0) dQ.push_front({u.fi,{nx,ny}});
  57.                 else dQ.push_back({d[nx][ny],{nx,ny}});
  58.             }
  59.         }
  60.     }
  61. }
  62. int main()
  63. {
  64.     fastio
  65.     while(cin>>n>>m)
  66.     {
  67.         if(!n && !m) break;
  68.         vector<vector<char>>A;
  69.         vector<vector<int>>d;
  70.         A.assign(n+10,vector<char>(m+10,'0'));
  71.         d.assign(n+10,vector<int>(m+10,1e9));
  72.         for(int i=1;i<=n;i++)
  73.             for(int j=1;j<=m;j++)
  74.                 cin>>A[i][j];
  75.         ans=1e9;
  76.         bfs(A,d);
  77.         if(ans==1e9) ans=-1;
  78.         cout<<ans<<'\n';
  79.     }
  80. }
  81.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VyuI1j
language:
C++14 (gcc 8.3)
created:
4 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!