# Algo proj second 2

Jul 31st, 2020
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. typedef pair<int, int> ii;
5. #define OO 0x7fffffff
6. #define S second
7. #define F first
8.
9. int dx[] = {1 , 0, 0,-1};
10. int dy[] = {0 ,-1, 1, 0};
11.
12. const int N = 1e3 + 3e1;
13. char Grid[N][N];
14. ii Tom ,Jerry;
15. int n ,m;
16.
17. inline bool isValid(int i ,int j){
18.     return (i > 0 && j > 0 && i < n && j < m && Grid[i][j] != 'W');
19. }
20.
21. vector< vector< int > > BFS( ii Start ){
22.     vector< vector< int > > Dist(n ,vector< int >(m ,OO));
23.     Dist[ Start.F ][ Start.S ] = 0;
24.     queue<ii> Q; Q.push(Start);
25.
26.     while( !Q.empty() ){
27.         ii front = Q.front(); Q.pop();
28.         int i = front.F ,j = front.S;
29.
30.         for(int move = 0 ; move < 4 ; move ++){
31.             int newI = i + dx[ move ];
32.             int newJ = j + dy[ move ];
33.
34.             if( isValid(newI ,newJ) && Dist[newI][newJ] == OO ){
35.                 Dist[newI][newJ] = Dist[i][j] + 1;
36.                 Q.push( ii(newI ,newJ) );
37.             }
38.         }
39.     }
40.
41.     return Dist;
42. }
43.
44. int main() {
45.     scanf("%d%d" ,&n ,&m);
46.     for(int i = 0 ; i < n ; i++){
47.         for(int j = 0 ; j < m ; j++){
48.             scanf("%c" ,&Grid[i][j]);
49.
50.             if( Grid[i][j] == 'J' ) Jerry = ii(i ,j);
51.             if( Grid[i][j] == 'T' ) Tom   = ii(i ,j);
52.         }
53.     }
54.
55.     vector< vector< int > > DistJerry = BFS(Jerry);
56.     vector< vector< int > > DistTom   = BFS( Tom );
57.
58.     bool JerryFlag = false;
59. // Check Rows
60.     for(int j = 0 ; j < m ; j++)
61.         if( DistJerry[0][j] <= DistTom[0][j] || DistJerry[n - 1][j] <= DistTom[n - 1][j] )
62.             JerryFlag = true;
63. // Check Columns
64.     for(int i = 0 ; i < n ; i++)
65.         if( DistJerry[i][0] <= DistTom[i][0] || DistJerry[i][m - 1] <= DistTom[i][m - 1] )
66.             JerryFlag = true;
67.
68.     puts( JerryFlag ? "Jerry" : "Tom" );
69.     return 0;
70. }
71.