Advertisement
ismaeil

I

Apr 18th, 2021
744
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int , int> ii;
  5. typedef vector< bool > vb;
  6. typedef vector< vb > vvb;
  7. typedef vector< int > vi;
  8. typedef vector< vi > vvi;
  9. #define OO int(1e9)
  10. #define S second
  11. #define F first
  12.  
  13. const int dx[] = {1 ,-1 , 0 ,0};
  14. const int dy[] = {0 , 0 ,-1 ,1};
  15. const int N = 1e3 + 3e1;
  16. char grid[N][N];
  17. int n ,m;
  18.  
  19. inline bool isValid(int i ,int j)
  20. {
  21.     return (0 < i && i <= n and 0 < j && j <= m and grid[i][j] == '.');
  22. }
  23.  
  24. vvi BFS(ii st)
  25. {
  26.     vvi Dist(n + 1 ,vi(m + 1 ,OO));
  27.     queue< ii > q; q.push(st);
  28.     Dist[st.F][st.S] = 0;
  29.    
  30.     while( !q.empty() )
  31.     {
  32.         ii front = q.front(); q.pop();
  33.         int i = front.F;
  34.         int j = front.S;
  35.        
  36.         for(int move = 0 ; move < 4 ; move ++)
  37.         {
  38.             int newI = i + dx[move];
  39.             int newJ = j + dy[move];
  40.            
  41.             if( isValid(newI ,newJ) && Dist[newI][newJ] == OO )
  42.             {
  43.                 Dist[newI][newJ] = Dist[i][j] + 1;
  44.                 q.push( ii(newI ,newJ) );
  45.             }
  46.         }
  47.     }
  48.    
  49.     return Dist;
  50. }
  51.  
  52. void Solve()
  53. {
  54.     scanf("%d%d" ,&n ,&m);
  55.     for(int i = 1 ; i <= n ; i++)
  56.         for(int j = 1 ; j <= m ; j++)
  57.             scanf("\n%c" ,&grid[i][j]);
  58.  
  59.     vvi tM = BFS( ii(1 ,1) );
  60.     vvi tS = BFS( ii(n ,1) );
  61.  
  62.     if( tM[n][m] < OO && tS[1][m] < OO )
  63.     {
  64.         vvi rM = BFS( ii(n ,m) );
  65.         vvi rS = BFS( ii(1 ,m) );
  66.         vvb vis(n + 1 ,vb(m + 1 ,false));
  67.  
  68.         int distM = tM[n][m];
  69.         int distS = tS[1][m];
  70.         for(int i = 1 ; i <= n ; i++)
  71.             for(int j = 1 ; j <= m ; j++)
  72.                 vis[i][j] = (rM[i][j] + tM[i][j] == distM || rS[i][j] + tS[i][j] == distS);
  73.  
  74.         int num = 0;
  75.         for(int i = 1 ; i <= n ; i++)
  76.             for(int j = 1 ; j <= m ; j++)
  77.                 num += vis[i][j];
  78.  
  79.         puts(num % 2 ? "Mouhanad" : "Salim");
  80.     }
  81.     else puts("tie");
  82. }
  83.  
  84. int main()
  85. {
  86.     freopen("chief.in" ,"r" ,stdin);
  87.    
  88.     int Tc;
  89.     scanf("%d" ,&Tc);
  90.  
  91.     while( Tc-- ) Solve();
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement