fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using  namespace std;
  5.  
  6. const int INF = 10000000;
  7. const string GAYBRASH = "GAYBRASH";
  8. const string LICHACK = "LICHACK";
  9.  
  10. struct node{
  11.     int x;
  12.     int y;
  13. };
  14.  
  15. vector<node> getChildrenBFS(char ** map, node parent, string hero){
  16.     string bannedChars = "R";
  17.     if(hero == LICHACK) bannedChars.push_back('e');
  18.     vector<node> children;
  19.     node leftChild = {parent.x - 1, parent.y};
  20.     node rightChild = {parent.x + 1, parent.y};
  21.     node downChild = {parent.x, parent.y + 1};
  22.     node upChild = {parent.x, parent.y - 1};
  23.     if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
  24.         children.push_back(leftChild);
  25.     }
  26.     if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
  27.         children.push_back(rightChild);
  28.     }
  29.     if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
  30.         children.push_back(downChild);
  31.     }
  32.     if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
  33.         children.push_back(upChild);
  34.     }
  35.     return children;
  36. }
  37.  
  38. void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
  39.     moves[currentNode.y][currentNode.x] = move;
  40.     move++;
  41.     vector<node> children = getChildrenBFS(map, currentNode, hero);
  42.     vector<node> queue;
  43.     for(auto e: children) {
  44.         if (move < moves[e.y][e.x]) {
  45.             dfsSecondPlayer(map, moves, hero, e, move);
  46.         }
  47.     }
  48. }
  49. void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
  50.     moves[currentNode.y][currentNode.x] = move;
  51.     move++;
  52.     vector<node> children = getChildrenBFS(map, currentNode, hero);
  53.     vector<node> queue;
  54.     for(auto e: children){
  55.         if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
  56.             dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
  57.         }
  58.     }
  59. }
  60. int main() {
  61.     int tests;
  62.     cin >> tests;
  63.     for(; tests > 0; tests--){
  64.         int m;
  65.         int n;
  66.         cin >> m >> n;
  67.         cin.ignore();
  68.         node g;
  69.         node l;
  70.         node e;
  71.         char **map = new char*[m];
  72.         for(int i = 0; i < m; i++){
  73.             map[i] = new char[n];
  74.         }
  75.         for(int i = 0; i < m; i++){
  76.             for(int j = 0; j < n; j++){
  77.                 map[i][j] = cin.get();
  78.                 switch(map[i][j]){
  79.                     case 'g':
  80.                         g.x = j;
  81.                         g.y = i;
  82.                         break;
  83.                     case 'l':
  84.                         l.x = j;
  85.                         l.y = i;
  86.                         break;
  87.                     case 'e':
  88.                         e.x = j;
  89.                         e.y = i;
  90.                         break;
  91.                 }
  92.             }
  93.             cin.ignore();
  94.         }
  95.         int **liChack = new int*[m];
  96.         for(int i = 0; i < m; i++){
  97.             liChack[i] = new int[n];
  98.         }
  99.         for(int i = 0; i < m; i++){
  100.             for(int j = 0; j < n; j++){
  101.                 liChack[i][j] = INF;
  102.             }
  103.         }
  104.         dfsSecondPlayer(map, liChack, LICHACK, l, 0);
  105.         int **gaybrash = new int*[m];
  106.         for(int i = 0; i < m; i++){
  107.             gaybrash[i] = new int[n];
  108.         }
  109.         for(int i = 0; i < m; i++){
  110.             for(int j = 0; j < n; j++){
  111.                 gaybrash[i][j] = INF;
  112.             }
  113.         }
  114.         dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
  115.         bool OK = gaybrash[e.y][e.x] != INF;
  116.         cout << (OK ? "YES" : "NO") << endl;
  117.         for(int i = 0; i < m; i++){
  118.             delete[] map[i];
  119.         }
  120.         delete[] map;
  121.         for(int i = 0; i < m; i++){
  122.             delete[] gaybrash[i];
  123.         }
  124.         delete[] gaybrash;
  125.         for(int i = 0; i < m; i++){
  126.             delete[] liChack[i];
  127.         }
  128.         delete[] liChack;
  129.     }
  130.     return 0;
  131. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
1
8 8
RRRRRRRR
R  Rg  R
R     RR
Re R R R
R   l  R
R R RR R
R     RR
RRRRRRRR
stdout
copy 
YES
https://ideone.com/XMpqb6
LeChuck’s Revenge
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!