fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define N int(500)
  4. using namespace std;
  5. struct dl
  6. {
  7.     ll u, v, val;
  8. };
  9. bool operator>(const dl& a, const dl& b)
  10. {
  11.     return a.val > b.val;
  12. }
  13. ll n, m;
  14. vector<dl>adj[N+10][N+10];
  15. char a[N+10][N+10];
  16. ll d[N+10][N+10];
  17. void bfs()
  18. {
  19.     for(int i=0; i<=n; i++)
  20.         for(int j=0; j<=m; j++) d[i][j]=1e9;
  21.  
  22.     d[0][0]=0;
  23.     priority_queue<dl, vector<dl>, greater<dl>>q;
  24.     q.push({0, 0, 0});
  25.     while(!q.empty())
  26.     {
  27.         dl top=q.top();
  28.         q.pop();
  29.         ll u=top.u;
  30.         ll v=top.v;
  31.         ll kc=top.val;
  32.         if(kc>d[u][v]) continue;
  33.         for(auto it:adj[u][v])
  34.         {
  35.             ll u1=it.u;
  36.             ll v1=it.v;
  37.             ll w=it.val;
  38.             if(d[u1][v1]>(d[u][v]+w))
  39.             {
  40.                 d[u1][v1]=d[u][v]+w;
  41.                 q.push({u1, v1, d[u1][v1]});
  42.  
  43.             }
  44.         }
  45.     }
  46. }
  47. int main()
  48. {
  49.     ios::sync_with_stdio(0);
  50.     cin.tie(0);
  51.     cout.tie(0);
  52.  
  53.     cin>>n>>m;
  54.     for(int i=1; i<=n; i++)
  55.         for(int j=1; j<=m; j++)
  56.         {
  57.             cin>>a[i][j];
  58.             if(a[i][j]=='\\')
  59.             {
  60.                 adj[i-1][j-1].push_back({i, j, 0});
  61.                 adj[i][j].push_back({i-1, j-1, 0});
  62.                 adj[i-1][j].push_back({i, j-1, 1});
  63.                 adj[i][j-1].push_back({i-1, j, 1});
  64.             }
  65.             else
  66.             {
  67.                 adj[i-1][j-1].push_back({i, j, 1});
  68.                 adj[i][j].push_back({i-1, j-1, 1});
  69.                 adj[i-1][j].push_back({i, j-1, 0});
  70.                 adj[i][j-1].push_back({i-1, j, 0});
  71.             }
  72.         }
  73.     bfs();
  74.     if (d[n][m] == 1e9) cout << "NO SOLUTION";
  75.     else cout << d[n][m];
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 10872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zYrP0q
language:
C++ (gcc 8.3)
created:
1 hour 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!