KishoreZE

Sol Igor and his way to work (MLE)

Dec 5th, 2020
1,158
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. char mat[1000][1000];
  22. int n, m;
  23. /*
  24. 0 - up
  25. 1 - right
  26. 2 - down
  27. 3 - left
  28. */
  29.  
  30. queue<pair<uint16_t, uint16_t>> nodes;
  31.  
  32. bool inbounds(int x, int y){
  33.     if(x<m && x>=0 && y<n && y>=0 && mat[y][x]!='*')
  34.         return true;
  35.     else
  36.         return false;
  37. }
  38.  
  39. void hasreached(int x, int y){
  40.     if(mat[y][x]=='T'){
  41.         cout<<"YES";
  42.         exit(0);
  43.     }
  44. }
  45.  
  46. void mark_tiles(){
  47.  
  48.     for(int n = nodes.size(), i=0; i<n; i++){
  49.         int x = nodes.front().first, y = nodes.front().second;
  50.         nodes.pop();
  51.         bool b1, b2;
  52.         b1 = b2 = true;
  53.         switch(mat[y][x]){
  54.             //turn horizontal
  55.             case 1:
  56.             for(int l=x-1, r=x+1; b1 || b2 == true; r++, l--){
  57.                 if(inbounds(l, y) && b1 && mat[y][l]!=2){
  58.                     hasreached(l, y);
  59.                     nodes.push(make_pair(l, y));
  60.                     mat[y][l] = 2;
  61.                 }
  62.                 else b1 = false;
  63.                 if(inbounds(r, y) && b2 && mat[y][r]!=2){
  64.                     hasreached(r, y);
  65.                     nodes.push(make_pair(r, y));
  66.                     mat[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 && mat[u][x]!=1){
  75.                     hasreached(x, u);
  76.                     nodes.push(make_pair(x, u));
  77.                     mat[u][x] = 1;
  78.                 }
  79.                 else b1 = false;
  80.                 if(inbounds(x, d) && b2 && mat[d][x]!=1){
  81.                     hasreached(x, d);
  82.                     nodes.push(make_pair(x, d));
  83.                     mat[d][x] = 1;
  84.                 }
  85.                 else b2 = false;
  86.             }
  87.             break;
  88.         }
  89.  
  90.     }
  91.  
  92.  
  93.  
  94. }
  95.  
  96. // ..S..****.T....****......
  97. int main(void){
  98.     usainbolt;
  99.     //file_read
  100.     cin>>n>>m;
  101.  
  102.     int h_x, h_y, b_x, b_y;
  103.     for(int i=0; i<n; i++){
  104.         for(int j=0; j<m; j++){
  105.             char inp;
  106.             cin>>inp;
  107.             mat[i][j] = inp;
  108.             if(mat[i][j]=='S')
  109.             {
  110.                 h_x = j;
  111.                 h_y = i;
  112.                 mat[i][j] = 1;
  113.             }
  114.         }
  115.     }
  116.     bool b1, b2, b3, b4;
  117.     b1 = b2 = b3 = b4 = true;
  118.  
  119.     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++){
  120.         if(inbounds(h_x, u) && b1){
  121.             hasreached(h_x, u);
  122.             nodes.push(make_pair(h_x, u));
  123.             mat[u][h_x] = 1;
  124.         }
  125.         else b1 = false;
  126.         if(inbounds(h_x, d) && b2){
  127.             hasreached(h_x, d);
  128.             nodes.push(make_pair(h_x, d));
  129.             mat[d][h_x] = 1;
  130.         }
  131.         else b2 = false;
  132.         if(inbounds(l, h_y) && b3){
  133.             hasreached(l, h_y);
  134.             nodes.push(make_pair(l, h_y));
  135.             mat[h_y][l] = 2;
  136.         }
  137.         else b3 = false;
  138.         if(inbounds(r, h_y) && b4){
  139.             hasreached(r, h_y);
  140.             nodes.push(make_pair(r, h_y));
  141.             mat[h_y][r] = 2;
  142.         }
  143.         else b4=false;
  144.     }
  145.  
  146.  
  147.     for(int i=0; i<2; i++){
  148.         mark_tiles();
  149.     }
  150.    
  151. /*    while (!nodes.empty())
  152.     {
  153.         cout << nodes.front().first << " " << nodes.front().second<<endl;
  154.         nodes.pop();
  155.     }
  156. */
  157.     cout << "NO";
  158.    
  159. }
RAW Paste Data