Advertisement
KishoreZE

B Igor and his way to work sol TLE

Dec 5th, 2020
1,111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.91 KB | None | 0 0
  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. int (*vis)[1000];
  24. int (*vis2)[1000];
  25.  
  26. /*
  27. 0 - up
  28. 1 - right
  29. 2 - down
  30. 3 - left
  31. */
  32.  
  33. bool inbounds(int x, int y){
  34.     if(x<m && x>=0 && y<n && y>=0 && mat[y][x]!='*')
  35.         return true;
  36.     else
  37.         return false;
  38. }
  39.  
  40. void hasreached(int x, int y){
  41.     if(mat[y][x]=='T'){
  42.         cout<<"YES";
  43.         exit(0);
  44.     }
  45. }
  46.  
  47. void mark_tiles(){
  48. for(int i=0; i<n; i++){
  49.     for(int j=0; j<m; j++){
  50.         if(vis[i][j]==0)
  51.             continue;
  52.         int x = j, y = i;
  53.         bool b1, b2;
  54.         b1 = b2 = true;
  55.         switch(vis[y][x]){
  56.             //turn horizontal
  57.             case 1:
  58.             for(int l=x-1, r=x+1; b1 || b2 == true; r++, l--){
  59.                 if(inbounds(l, y) && b1 && vis[y][l]!=2){
  60.                     hasreached(l, y);
  61.                     vis2[y][l] = 2;
  62.                 }
  63.                 else b1 = false;
  64.                 if(inbounds(r, y) && b2 && vis[y][r]!=2){
  65.                     hasreached(r, y);
  66.                     vis2[y][r] = 2;
  67.                 }
  68.                 else b2 = false;
  69.             }
  70.             break;
  71.             //turn vertical
  72.             case 2:
  73.             for(int u=y-1, d=y+1; b1 || b2 == true; d++, u--){
  74.                 if(inbounds(x, u) && b1 && vis[u][x]!=1){
  75.                     hasreached(x, u);
  76.                     vis2[u][x] = 1;
  77.                 }
  78.                 else b1 = false;
  79.                 if(inbounds(x, d) && b2 && vis[d][x]!=1){
  80.                     hasreached(x, d);
  81.                     vis2[d][x] = 1;
  82.                 }
  83.                 else b2 = false;
  84.             }
  85.             break;
  86.         }
  87.         vis[i][j] = 0;
  88.     }
  89. }
  90.     int (*temp)[1000] = vis;
  91.     vis = vis2;
  92.     vis2 = temp;
  93.  
  94. }
  95.  
  96. // ..S..****.T....****......
  97. int main(void){
  98.     usainbolt;
  99.     //file_read
  100.     cin>>n>>m;
  101.     vis = (int(*)[1000])calloc(1000, 1000*4);
  102.     vis2 = (int(*)[1000])calloc(1000, 4*1000);
  103.     int h_x, h_y, b_x, b_y;
  104.     for(int i=0; i<n; i++){
  105.         for(int j=0; j<m; j++){
  106.             char inp;
  107.             cin>>inp;
  108.             mat[i][j] = inp;
  109.             if(mat[i][j]=='S')
  110.             {
  111.                 h_x = j;
  112.                 h_y = i;
  113.                 vis[i][j] = 1;
  114.             }
  115.         }
  116.     }
  117.     bool b1, b2, b3, b4;
  118.     b1 = b2 = b3 = b4 = true;
  119.  
  120.     for(int u=h_y-1, d=h_y+1, l=h_x-1, r=h_x+1; b1 || b2 || b3 || b4 == true; r++, l--, u--, d++){
  121.         if(inbounds(h_x, u) && b1){
  122.             hasreached(h_x, u);
  123.             vis[u][h_x] = 1;
  124.         }
  125.         else b1 = false;
  126.         if(inbounds(h_x, d) && b2){
  127.             hasreached(h_x, d);
  128.             vis[d][h_x] = 1;
  129.         }
  130.         else b2 = false;
  131.         if(inbounds(l, h_y) && b3){
  132.             hasreached(l, h_y);
  133.             vis[h_y][l] = 2;
  134.         }
  135.         else b3 = false;
  136.         if(inbounds(r, h_y) && b4){
  137.             hasreached(r, h_y);
  138.             vis[h_y][r] = 2;
  139.         }
  140.         else b4=false;
  141.     }
  142.  
  143.     for(int i=0; i<2; i++){
  144.         /*
  145.         cout<<endl<<endl;
  146.         for(int i=0; i<n; i++){
  147.             for(int j=0; j<m; j++){
  148.                 cout<<vis[i][j];
  149.             }
  150.             cout<<endl;
  151.         }
  152.         */
  153.         mark_tiles();
  154.     }
  155.    
  156.     cout << "NO";
  157.    
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement