Advertisement
Guest User

Untitled

a guest
Apr 25th, 2020
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.34 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayDeque;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.StringTokenizer;
  9.  
  10. public class RobotsOnAGrid {
  11.     public static void main(String[] args) throws IOException {
  12.         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
  13.         int t = Integer.parseInt(f.readLine());
  14.         PrintWriter out = new PrintWriter(System.out);
  15.         for (int t1 = 0; t1 < t; t1++) {
  16.             StringTokenizer tokenizer = new StringTokenizer(f.readLine());
  17.             int n = Integer.parseInt(tokenizer.nextToken());
  18.             int m = Integer.parseInt(tokenizer.nextToken());
  19.             char[][] map = new char[n][m];
  20.             boolean[] isBlack = new boolean[n * m];
  21.             ArrayList<ArrayList<Integer>> isParentOf = new ArrayList<ArrayList<Integer>>();
  22.             for (int i = 0; i < n; i++) {
  23.                 for (int j = 0; j < m; j++) {
  24.                     isParentOf.add(new ArrayList<Integer>());
  25.                 }
  26.             }
  27.             for (int i = 0; i < n; i++) {
  28.                 char[] seq = f.readLine().toCharArray();
  29.                 for (int j = 0; j < m; j++) {
  30.                     if (seq[j] == '0') {
  31.                         isBlack[i * m + j] = true;
  32.                     }
  33.                 }
  34.             }
  35.             for (int i = 0; i < n; i++) {
  36.                 char[] seq = f.readLine().toCharArray();
  37.                 for (int j = 0; j < m; j++) {
  38.                     map[i][j] = seq[j];
  39.                     if (seq[j] == 'R') {
  40.                         isParentOf.get(i * m + j + 1).add(i * m + j);
  41.                     } else if (seq[j] == 'L') {
  42.                         isParentOf.get(i * m + j  - 1).add(i * m + j);
  43.                     } else if (seq[j] == 'U') {
  44.                         isParentOf.get((i - 1) * m + j).add(i * m + j);
  45.                     } else {
  46.                         isParentOf.get((i + 1) * m + j).add(i * m + j);
  47.                     }
  48.                 }
  49.             }
  50.  
  51.             ArrayList<int[]> cycleVertexAndSize = new ArrayList<int[]>();
  52.             boolean[][] visited = new boolean[n][m];
  53.             boolean[][] onStack = new boolean[n][m];
  54.             for (int i = 0; i < n; i++) {
  55.                 for (int j = 0; j < m; j++) {
  56.                     if (!visited[i][j]) {
  57.                         ArrayDeque<int[]> stack = new ArrayDeque<int[]>();
  58.                         dfsCycle(cycleVertexAndSize, map, i, j, visited, onStack, stack);
  59.                     }
  60.                 }
  61.             }
  62.  
  63.             int robots = 0;
  64.             int blackRobots = 0;
  65.             boolean[] visited2 = new boolean[n * m];
  66.             for (int[] cycle : cycleVertexAndSize) {
  67.                 robots += cycle[2];
  68.                 boolean[] moduloBlack = new boolean[cycle[2]];
  69.                 dfsFindBlackInCycle(cycle[0] * m + cycle[1], isParentOf, moduloBlack, 0, isBlack, visited2);
  70.                 for (int i = 0; i < cycle[2]; i++) {
  71.                     if (moduloBlack[i]) {
  72.                         blackRobots++;
  73.                     }
  74.                 }
  75.             }
  76.  
  77.             out.println(robots + " " + blackRobots);
  78.         }
  79.  
  80.         out.close();
  81.     }
  82.  
  83.     private static void dfsFindBlackInCycle(int vertex, ArrayList<ArrayList<Integer>> parentOf, boolean[] moduloBlack, int path, boolean[] isBlack, boolean[] visited) {
  84.         visited[vertex] = true;
  85.         if (isBlack[vertex]) {
  86.             moduloBlack[path % moduloBlack.length] = true;
  87.         }
  88.         for (int children : parentOf.get(vertex)) {
  89.             if (!visited[children]) {
  90.                 dfsFindBlackInCycle(children, parentOf, moduloBlack, path + 1, isBlack, visited);
  91.             }
  92.         }
  93.     }
  94.  
  95.     private static void dfsCycle(ArrayList<int[]> cycleVertexAndSize, char[][] map, int x, int y, boolean[][] visited, boolean[][] onStack, ArrayDeque<int[]> stack) {
  96.         visited[x][y] = true;
  97.         onStack[x][y] = true;
  98.         int[] ar = {x, y};
  99.         stack.push(ar);
  100.         ar = null;
  101.  
  102.         int nextX;
  103.         int nextY;
  104.         if (map[x][y] == 'R') {
  105.             nextX = x;
  106.             nextY = y + 1;
  107.         } else if (map[x][y] == 'L') {
  108.             nextX = x;
  109.             nextY = y - 1;
  110.         } else if (map[x][y] == 'U') {
  111.             nextX = x - 1;
  112.             nextY = y;
  113.         } else {
  114.             nextX = x + 1;
  115.             nextY = y;
  116.         }
  117.  
  118.         if (!visited[nextX][nextY]) {
  119.             dfsCycle(cycleVertexAndSize, map, nextX ,nextY, visited, onStack, stack);
  120.         } else {
  121.             if (onStack[nextX][nextY]) {
  122.                 int circleSize = 1;
  123.                 while (!(stack.peek()[0] == nextX && stack.peek()[1] == nextY)) {
  124.                     stack.pop();
  125.                     circleSize++;
  126.                 }
  127.  
  128.                 int[] vertexAndSize = new int[3];
  129.                 vertexAndSize[0] = nextX;
  130.                 vertexAndSize[1] = nextY;
  131.                 vertexAndSize[2] = circleSize;
  132.                 cycleVertexAndSize.add(vertexAndSize);
  133.                 vertexAndSize = null;
  134.             }
  135.         }
  136.  
  137.         if (!stack.isEmpty() && stack.peek()[0] == x && stack.peek()[1] == y) {
  138.             stack.pop();
  139.         }
  140.         onStack[x][y] = false;
  141.     }
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement