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