Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int , int> ii;
- typedef vector< bool > vb;
- typedef vector< vb > vvb;
- typedef vector< int > vi;
- typedef vector< vi > vvi;
- #define OO int(1e9)
- #define S second
- #define F first
- const int dx[] = {1 ,-1 , 0 ,0};
- const int dy[] = {0 , 0 ,-1 ,1};
- const int N = 1e3 + 3e1;
- char grid[N][N];
- int n ,m;
- inline bool isValid(int i ,int j)
- {
- return (0 < i && i <= n and 0 < j && j <= m and grid[i][j] == '.');
- }
- vvi BFS(ii st)
- {
- vvi Dist(n + 1 ,vi(m + 1 ,OO));
- queue< ii > q; q.push(st);
- Dist[st.F][st.S] = 0;
- while( !q.empty() )
- {
- ii front = q.front(); q.pop();
- int i = front.F;
- int j = front.S;
- for(int move = 0 ; move < 4 ; move ++)
- {
- int newI = i + dx[move];
- int newJ = j + dy[move];
- if( isValid(newI ,newJ) && Dist[newI][newJ] == OO )
- {
- Dist[newI][newJ] = Dist[i][j] + 1;
- q.push( ii(newI ,newJ) );
- }
- }
- }
- return Dist;
- }
- void Solve()
- {
- scanf("%d%d" ,&n ,&m);
- for(int i = 1 ; i <= n ; i++)
- for(int j = 1 ; j <= m ; j++)
- scanf("\n%c" ,&grid[i][j]);
- vvi tM = BFS( ii(1 ,1) );
- vvi tS = BFS( ii(n ,1) );
- if( tM[n][m] < OO && tS[1][m] < OO )
- {
- vvi rM = BFS( ii(n ,m) );
- vvi rS = BFS( ii(1 ,m) );
- vvb vis(n + 1 ,vb(m + 1 ,false));
- int distM = tM[n][m];
- int distS = tS[1][m];
- for(int i = 1 ; i <= n ; i++)
- for(int j = 1 ; j <= m ; j++)
- vis[i][j] = (rM[i][j] + tM[i][j] == distM || rS[i][j] + tS[i][j] == distS);
- int num = 0;
- for(int i = 1 ; i <= n ; i++)
- for(int j = 1 ; j <= m ; j++)
- num += vis[i][j];
- puts(num % 2 ? "Mouhanad" : "Salim");
- }
- else puts("tie");
- }
- int main()
- {
- freopen("chief.in" ,"r" ,stdin);
- int Tc;
- scanf("%d" ,&Tc);
- while( Tc-- ) Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement