KishoreZE

Sol: B. Igor and his way to work (TLE)

Dec 3rd, 2020
1,501
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7. typedef pair<int, int> pi;
  8.  
  9. #define f first
  10. #define s second
  11. #define pb push_back
  12. #define mp make_pair
  13. #define loop(n) for(int i=0; i<n; i++)
  14. #define rep(i, a, n) for(int i=a; i<n; i++)
  15. #define file_read freopen("input.txt", "r", stdin); \
  16.                   freopen("output.txt", "w", stdout);
  17. #define tc int t; cin>>t; while(t--)
  18. #define endl "\n"
  19. #define usainbolt cin.tie(0) -> sync_with_stdio(0)
  20.  
  21. int mat[1000][1000];
  22. int n, m;
  23.  
  24. /*
  25. 0 - up
  26. 1 - right
  27. 2 - down
  28. 3 - left
  29. */
  30.  
  31. int offset[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
  32. int opp_dir[4] = {2, 3, 0, 1};
  33.  
  34. bool inbounds(int x, int y, int direction){
  35.     int offset_x = offset[direction][0], offset_y = offset[direction][1];
  36.     x += offset_x;
  37.     y += offset_y;
  38.     if(x<m && x>=0 && y<n && y>=0){
  39.         if(mat[y][x]!='*')
  40.             return true;
  41.         else
  42.             return false;
  43.     }
  44.     return false;
  45. }
  46.  
  47. bool possible = false;
  48.  
  49. void solve_rec(int cur_dir, int x, int y, int turns){
  50.  
  51.     if(mat[y][x]=='T'){
  52.         possible = true;
  53.         return;
  54.     }
  55.  
  56.     for(; inbounds(x, y, cur_dir);){
  57.         x += offset[cur_dir][0];
  58.         y += offset[cur_dir][1];
  59.         for(int i=0; i<4 && turns <= 2; i++){
  60.             if(i==cur_dir || i==opp_dir[cur_dir])
  61.                 continue;
  62.             if(turns < 2 && inbounds(x, y, i))
  63.                 solve_rec(i, x+offset[i][0], y+offset[i][1],turns+1);
  64.         }  
  65.         if(mat[y][x]=='T'){
  66.             possible = true;
  67.             return;
  68.         }
  69.     }
  70.  
  71. }
  72. // ..S..****.T....****......
  73. int main(void){
  74.     usainbolt;
  75.     //file_read
  76.     cin>>n>>m;
  77.  
  78.     int h_x, h_y, b_x, b_y;
  79.     for(int i=0; i<n; i++){
  80.         for(int j=0; j<m; j++){
  81.             char inp;
  82.             cin>>inp;
  83.             mat[i][j] = inp;
  84.             if(mat[i][j]=='S')
  85.             {
  86.                 h_x = j;
  87.                 h_y = i;
  88.             }
  89.         }
  90.     }
  91.  
  92.     solve_rec(0, h_x, h_y, 0);
  93.     solve_rec(1, h_x, h_y, 0);
  94.     solve_rec(2, h_x, h_y, 0);
  95.     solve_rec(3, h_x, h_y, 0);
  96.  
  97.     if(possible)
  98.         cout << "YES";
  99.     else
  100.         cout << "NO";
  101.    
  102. }
RAW Paste Data