fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6. public class Main{
  7.  
  8.     private static class Node {
  9.         private int i;
  10.         private int j;
  11.  
  12.         private Node(int i, int j) {
  13.             this.i = i;
  14.             this.j = j;
  15.         }
  16.     }
  17.     private static void fill(int[][] a, int value) {
  18.         for (int i = 0; i < a.length; i++) {
  19.             for (int j = 0; j < a[i].length; j++) {
  20.                 a[i][j] = value;
  21.             }
  22.         }
  23.     }
  24.  
  25.     private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
  26.         Queue<Node> queue = new LinkedList<>();
  27.         moves[start.i][start.j] = 0;
  28.         queue.add(start);
  29.         while (!queue.isEmpty()) {
  30.             Node curNode = queue.poll();
  31.             int i = curNode.i;
  32.             int j = curNode.j;
  33.             if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
  34.                 moves[i - 1][j] = moves[i][j] + 1;
  35.                 queue.add(new Node(i - 1, j));
  36.             }
  37.             if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
  38.                 moves[i + 1][j] = moves[i][j] + 1;
  39.                 queue.add(new Node(i + 1, j));
  40.             }
  41.             if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
  42.                 moves[i][j - 1] = moves[i][j] + 1;
  43.                 queue.add(new Node(i, j - 1));
  44.             }
  45.             if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
  46.                 moves[i][j + 1] = moves[i][j] + 1;
  47.                 queue.add(new Node(i, j + 1));
  48.             }
  49.         }
  50.     }
  51.  
  52.     private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
  53.         Queue<Node> queue = new LinkedList<>();
  54.         queue.add(start);
  55.         moves[start.i][start.j] = 0;
  56.         while (!queue.isEmpty()) {
  57.             Node curNode = queue.poll();
  58.             int i = curNode.i;
  59.             int j = curNode.j;
  60.             if (map[i][j] == 'e') {
  61.                 return true;
  62.             }
  63.             if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
  64.                 moves[i - 1][j] = moves[i][j] + 1;
  65.                 queue.add(new Node(i - 1, j));
  66.             }
  67.             if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
  68.                 moves[i + 1][j] = moves[i][j] + 1;
  69.                 queue.add(new Node(i + 1, j));
  70.             }
  71.             if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
  72.                 moves[i][j - 1] = moves[i][j] + 1;
  73.                 queue.add(new Node(i, j - 1));
  74.             }
  75.             if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
  76.                 moves[i][j + 1] = moves[i][j] + 1;
  77.                 queue.add(new Node(i, j + 1));
  78.             }
  79.         }
  80.         return false;
  81.     }
  82.  
  83.     public static void main(String[] args) throws IOException{
  84.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  85.         int tests = Integer.parseInt(bufferedReader.readLine());
  86.         for (int r = 0; r < tests; r++) {
  87.             String[] sizes = bufferedReader.readLine().split(" ");
  88.             int n = Integer.parseInt(sizes[0]);
  89.             int m = Integer.parseInt(sizes[1]);
  90.             char[][] map = new char[n][m];
  91.             Node g = null;
  92.             Node l = null;
  93.             Node e = null;
  94.             for (int i = 0; i < n; i++) {
  95.                 map[i] = bufferedReader.readLine().toCharArray();
  96.                 for (int j = 0; j < m; j++) {
  97.                     if (map[i][j] == 'g') {
  98.                         g = new Node(i, j);
  99.                     }
  100.                     else if (map[i][j] == 'l') {
  101.                         l = new Node(i, j);
  102.                     }
  103.                     else if (map[i][j] == 'e') {
  104.                         e = new Node(i, j);
  105.                     }
  106.                 }
  107.             }
  108.             int[][] secondPlayerDistances = new int[n][m];
  109.             fill(secondPlayerDistances, Integer.MAX_VALUE);
  110.             bfsSecondPlayer(map, secondPlayerDistances, l);
  111.             int[][] firstPlayerDistances = new int[n][m];
  112.             fill(firstPlayerDistances, Integer.MAX_VALUE);
  113.             boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
  114.             System.out.println(ok ? "YES" : "NO");
  115.         }
  116.     }
  117. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
3
6 7
RRRRRRR
R_e___R
R_____R
R_RRR_R
R_gRl_R
RRRRRRR
4 5
RRRRR
R__eR
Rgl_R
RRRRR
9 13
RRRRRRRRRRRRR
R_____R___R_R
R_R_R_R_R_R_R
R___RRR_R_R_R
R_RRR___ReR_R
R_R___R_R_R_R
R_R_RRRRR_R_R
R_g________lR
RRRRRRRRRRRRR
stdout
copy 
YES
NO
YES
https://ideone.com/C5vf3r
language:
Java (HotSpot 12)
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!