fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <string>
  3. using namespace std;
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define si(X) scanf("%d", &(X))
  7. #define sll(X) scanf("%lld",&(X))
  8.  
  9. const int M = 3e3 + 5;
  10. const int MAXX = 1e8;
  11.  
  12. int dp[M][M][2];
  13.  
  14. set<int> evenRows, evenCols, oddRows, oddCols;
  15. int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
  16. int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
  17.  
  18. int n, m;
  19.  
  20. bool inside(int x, int y){
  21.     return (x >= 1 && x <= n && y >= 1 && y <= m);
  22. }
  23.  
  24. int main(){
  25.  
  26.     for(int i = 1 ; i < M ; i++){
  27.         for(int j = 1 ; j < M ; j++){
  28.             for(int k = 0 ; k < 3 ; k++){
  29.                 dp[i][j][k] = MAXX;
  30.             }
  31.         }
  32.     }
  33.  
  34.     int k;
  35.     cin >> n >> m >> k;
  36.  
  37.  
  38.     for(int i = 1 ; i <= k ; i++){
  39.         int x, y;
  40.         char ch;
  41.         si(x);  si(y);  cin >> ch;
  42.         if(ch == 'R'){
  43.             evenRows.insert(x);
  44.             oddCols.insert(y);
  45.            // cout<<"even row "<<x <<" odd col "<<y<<endl;
  46.         }
  47.         else{
  48.             oddRows.insert(x);
  49.             evenCols.insert(y);
  50.            // cout<<"odd row "<<x <<" even col "<<y<<endl;
  51.  
  52.         }
  53.     }
  54.  
  55.     dp[1][1][0] = 0;
  56.     // x, y, even, odd
  57.     queue<pair<int, pair<int, int> > > Q;
  58.     Q.push({1, {1, 0}});
  59.  
  60.    // set<pair<int, pair<int, int> > > se;
  61.    // se.insert({1, {1, 0}});
  62.  
  63.     while(Q.size()){
  64.         pair<int, pair<int, int> > p = Q.front();
  65.  
  66.         int curX = p.first;
  67.         int curY = p.second.first;
  68.         int evenn = p.second.second;
  69.         Q.pop();
  70.  
  71.         if(dp[curX][curY][evenn] >= MAXX) continue;
  72.  
  73.  
  74.         for(int d = 0 ; d < 4 ; d++){
  75.             int nx = curX + dx[d];
  76.             int ny = curY + dy[d];
  77.             if(!inside(nx, ny)) continue;
  78.  
  79.             if(evenn){
  80.                 // odd should not have it
  81.                 if(oddRows.count(nx) || oddCols.count(ny)){
  82.                     continue;
  83.                 }
  84.                 if(dp[nx][ny][1 - evenn] >= MAXX){
  85.                     dp[nx][ny][1 - evenn] = dp[curX][curY][evenn] + 1;
  86.                     Q.push({nx, {ny, 1 - evenn}});
  87.                 }
  88.             }
  89.             else{
  90.                 // even should not have it
  91.                 if(evenRows.count(nx) || evenCols.count(ny)){
  92.                     continue;
  93.                 }
  94.                 if(dp[nx][ny][1 - evenn] >= MAXX){
  95.                     dp[nx][ny][1 - evenn] = dp[curX][curY][evenn] + 1;
  96.                     Q.push({nx, {ny, 1 - evenn}});
  97.                 }
  98.             }
  99.            // cout<<"ok "<<nx<<". "<<ny<<" "<<1 - evenn<<" "<<dp[nx][ny][1 - evenn]<<endl;
  100.         }
  101.  
  102.  
  103.     }
  104.  
  105.     int ans = min(dp[n][m][0], dp[n][m][1]);
  106.     if(ans >= MAXX){
  107.         ans = -1;
  108.     }
  109.     cout<<ans;
  110.  
  111.  
  112. }
Success #stdin #stdout 0.02s 74000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lZFiTV
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!