fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <queue>
  3. #define MAXN 100
  4. using namespace std;
  5.  
  6. int monster_level[MAXN][MAXN]; //monster visited time
  7. int human_level[MAXN][MAXN];   //human visited time
  8. int grid[MAXN][MAXN];
  9.  
  10. int row, col;
  11.  
  12.  
  13. // check if it is possible to move to (x, y)
  14. bool isValidMove(int x, int y)
  15. {
  16.     if (x < 0 || x >= row || y < 0 || y >= col)
  17.         return false;
  18.     return true;
  19. }
  20. //check the cell if it is visited by monster before human
  21. bool is_Forbidden(int x, int y)
  22. {
  23.     if(monster_level[x][y]<=human_level[x][y]) return true;
  24.     return false;
  25. }
  26.  
  27. //check escape
  28. bool is_escape(int x, int y)
  29. {
  30.     if(x==0 || y==0 || x==row-1 || y==col-1) return true;
  31.     return false;
  32. }
  33.  
  34. // BFS traversal of the grid
  35. void monster_BFS(vector<pair<int,int>>monsters, int row, int col)
  36. {
  37.     int x, y;
  38.     queue<pair<int, int>> q;
  39.  
  40.     for(pair<int,int>par:monsters){
  41.     	// mark the starting point as visited
  42.     q.push(par);
  43.     monster_level[par.first][par.second]=0;
  44.     grid[par.first][par.second] = -2; //-2 for monster visited
  45.     }
  46.  
  47.     int dx[] = {-1, 1, 0, 0};
  48.     int dy[] = {0, 0, -1, 1};
  49.  
  50.     while (!q.empty())
  51.     {
  52.         x = q.front().first;
  53.         y = q.front().second;
  54.         q.pop();
  55.  
  56.         for (int i = 0; i < 4; i++)
  57.         {
  58.             int newX = x + dx[i];
  59.             int newY = y + dy[i];
  60.  
  61.             if (isValidMove(newX, newY) && grid[newX][newY] != -1 && grid[newX][newY] != -2)
  62.             {
  63.             //	cout<<newX<<" "<<newY<<endl;
  64.                 q.push({newX, newY});
  65.                 grid[newX][newY] = -2;
  66.                 monster_level[newX][newY] = monster_level[x][y] + 1;
  67.             }
  68.         }
  69.     }
  70. }
  71. //cout<<"....."<<endl;
  72. void human_BFS(int startX, int startY,int row, int col)
  73. {
  74.     int x, y;
  75.     queue<pair<int, int>> q;
  76.  
  77.     // mark the starting point as visited
  78.     q.push({startX, startY});
  79.     grid[startX][startY] = 1; //1 for human visited
  80.     human_level[startX][startY]=0;
  81.     int dx[] = {-1, 1, 0, 0};
  82.     int dy[] = {0, 0, -1, 1};
  83.  
  84.     while (!q.empty())
  85.     {
  86.         x = q.front().first;
  87.         y = q.front().second;
  88.         q.pop();
  89.  
  90.         for (int i = 0; i < 4; i++)
  91.         {
  92.             int newX = x + dx[i];
  93.             int newY = y + dy[i];
  94.  
  95.  
  96.             if (isValidMove(newX, newY) && grid[newX][newY] != -1 && grid[newX][newY] != 1 && !is_Forbidden(newX, newY))
  97.             {
  98.             	//cout<<newX<<" "<<newY<<endl;
  99.             	if(is_escape(newX,newY))
  100.                 {
  101.                     cout<<newX<<" "<<newY<<" "<<"YES"<<endl;
  102.                     return;
  103.                 }
  104.  
  105.                 q.push({newX, newY});
  106.                 human_level[newX][newY]=human_level[x][y]+1;
  107.                 grid[newX][newY] = 1;
  108.             }
  109.         }
  110.     }
  111.     cout<<"NO";
  112. }
  113. int main()
  114. {
  115.     /*
  116. 5 8
  117. ########
  118. #M..A..#
  119. #.#.M#.#
  120. #M#..#..
  121. #.######
  122.     */
  123.     vector<pair<int, int>> monsters;
  124.     pair<int,int>start;
  125.     cin>>row>>col;
  126.     for(int r=0; r<row; r++)
  127.     {
  128.         string s;
  129.         cin>>s;
  130.         for(int c=0; c<col; c++)
  131.         {
  132.             if(s[c]=='#')
  133.                 grid[r][c]=-1;
  134.             else if(s[c]=='.')
  135.                 grid[r][c]=1;
  136.             else if(s[c]=='M')
  137.             {
  138.                 grid[r][c]=-2;
  139.                 pair<int,int>monster=make_pair(r,c);
  140.                 monsters.push_back(monster);
  141.             }
  142.             else if(s[c]=='A')
  143.             {
  144.                 grid[r][c]=1;
  145.                 start=make_pair(r,c);
  146.             }
  147.         }
  148.     }
  149.     for(int i=0;i<row;i++){
  150. 	//for(int j=0;j<col;j++){
  151. 		//human_level[i][j]=INT_MAX;
  152. 	//}
  153. }
  154.  
  155.    monster_BFS(monsters,row,col);
  156.    human_BFS(start.first,start.second,row,col);
  157.    for(int r=0;r<row;r++){
  158.    	for(int c=0;c<col;c++){
  159.    	//	cout<<"r:"<<r<<"c:"<<c<<" "<<human_level[r][c]<<" "<<monster_level[r][c]<<endl;
  160.    	}
  161.    }
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
5 8
########
#M..A..#
#.#.M..#
#M#..#..
#.######
stdout
copy 
3 7 YES
https://ideone.com/Zcwq6d
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!