fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define fi first
  5. #define se second
  6. #define pii pair<int,int>
  7. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8. using namespace std;
  9.  
  10.  
  11.  
  12. const int MOD=998244353;
  13. const int MAX=1e5+1;
  14. const int inf=1e6;
  15.  
  16. int add(int a,int b){ return ((a%MOD)+(b%MOD))%MOD;}
  17. int mul(int a,int b){ return ((a%MOD)*(b%MOD))%MOD;}
  18. int sub(int x,int y){ return ((x - y) % MOD) + ((x >= y) ? 0 : MOD);}
  19. int ceil_div(int a,int b) {return a%b==0?a/b:(a/b)+1;}
  20.  
  21. int be_itr(int x,int n)
  22. {
  23.     int res=1;
  24.     while(n)
  25.     {
  26.         if(n%2==1){
  27.             res*=x;
  28.             res%=MOD;
  29.         }
  30.         n/=2;
  31.         x*=x;
  32.         x%=MOD;
  33.     }
  34.     return res;
  35. }
  36.  
  37. int dx[]={-1,0,1,0};
  38. int dy[]={0,1,0,-1};
  39.  
  40. int n,m;
  41. bool val(int x, int y)
  42. {
  43.     if(x<1 || y<1 || x>n || y>m)return false;
  44.     return true;
  45. }
  46.  
  47.  
  48. void solve()
  49. {
  50.     cin>>n>>m;
  51.     int a[n+1][m+1];
  52.     for(int i=1;i<=n;i++)
  53.     {
  54.         for(int j=1;j<=m;j++)cin>>a[i][j];
  55.     }
  56.     int dis[n+1][m+1];
  57.     for(int i=1;i<=n;i++)
  58.     {
  59.     	for(int j=1;j<=m;j++)dis[i][j]=inf;
  60.     }
  61.  
  62.     queue<pair<int,int>>q;
  63.     q.push({1,1});
  64.     dis[1][1]=0;
  65.  
  66.     while(!q.empty())
  67.     {
  68.         int x=q.front().fi;
  69.         int y=q.front().se;
  70.         q.pop();
  71.         for(int i=0;i<4;i++)
  72.         {
  73.             int nx=x+dx[i],ny=y+dy[i];
  74.             if(val(nx,ny))
  75.             {
  76.                 if(a[nx][ny]==1)
  77.                 {
  78.                     int k1=dis[x][y]+1;
  79.                     if(k1<dis[nx][ny]){
  80.                         dis[nx][ny]=k1;
  81.                         q.push({nx,ny});
  82.                     }
  83.                 }
  84.                 else{
  85.                     if(dis[x][y]<dis[nx][ny])
  86.                     {
  87.                         dis[nx][ny]=dis[x][y];
  88.                         q.push({nx,ny});
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.     }
  94.     cout<<dis[n][m]<<endl;
  95. }
  96.  
  97. int32_t main()
  98. {
  99.     IOS;
  100.     int t=1;//cin>>t;
  101.     while(t--)
  102.     {
  103.         solve();
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
3 3
0 1 1
1 1 0
1 1 0
stdout
copy 
2
https://ideone.com/QubDF6
language:
C++ (gcc 8.3)
created:
1 year 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!