Advertisement
ismaeil

Algo proj second 2

Jul 31st, 2020
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement