Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.io.PrintWriter;
- import java.util.ArrayDeque;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.StringTokenizer;
- public class RobotsOnAGrid {
- public static void main(String[] args) throws IOException {
- BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
- int t = Integer.parseInt(f.readLine());
- PrintWriter out = new PrintWriter(System.out);
- for (int t1 = 0; t1 < t; t1++) {
- StringTokenizer tokenizer = new StringTokenizer(f.readLine());
- int n = Integer.parseInt(tokenizer.nextToken());
- int m = Integer.parseInt(tokenizer.nextToken());
- char[][] map = new char[n][m];
- boolean[] isBlack = new boolean[n * m];
- ArrayList<ArrayList<Integer>> isParentOf = new ArrayList<ArrayList<Integer>>();
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- isParentOf.add(new ArrayList<Integer>());
- }
- }
- for (int i = 0; i < n; i++) {
- char[] seq = f.readLine().toCharArray();
- for (int j = 0; j < m; j++) {
- if (seq[j] == '0') {
- isBlack[i * m + j] = true;
- }
- }
- }
- for (int i = 0; i < n; i++) {
- char[] seq = f.readLine().toCharArray();
- for (int j = 0; j < m; j++) {
- map[i][j] = seq[j];
- if (seq[j] == 'R') {
- isParentOf.get(i * m + j + 1).add(i * m + j);
- } else if (seq[j] == 'L') {
- isParentOf.get(i * m + j - 1).add(i * m + j);
- } else if (seq[j] == 'U') {
- isParentOf.get((i - 1) * m + j).add(i * m + j);
- } else {
- isParentOf.get((i + 1) * m + j).add(i * m + j);
- }
- }
- }
- ArrayList<int[]> cycleVertexAndSize = new ArrayList<int[]>();
- boolean[][] visited = new boolean[n][m];
- boolean[][] onStack = new boolean[n][m];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (!visited[i][j]) {
- ArrayDeque<int[]> stack = new ArrayDeque<int[]>();
- dfsCycle(cycleVertexAndSize, map, i, j, visited, onStack, stack);
- }
- }
- }
- int robots = 0;
- int blackRobots = 0;
- boolean[] visited2 = new boolean[n * m];
- for (int[] cycle : cycleVertexAndSize) {
- robots += cycle[2];
- boolean[] moduloBlack = new boolean[cycle[2]];
- dfsFindBlackInCycle(cycle[0] * m + cycle[1], isParentOf, moduloBlack, 0, isBlack, visited2);
- for (int i = 0; i < cycle[2]; i++) {
- if (moduloBlack[i]) {
- blackRobots++;
- }
- }
- }
- out.println(robots + " " + blackRobots);
- }
- out.close();
- }
- private static void dfsFindBlackInCycle(int vertex, ArrayList<ArrayList<Integer>> parentOf, boolean[] moduloBlack, int path, boolean[] isBlack, boolean[] visited) {
- visited[vertex] = true;
- if (isBlack[vertex]) {
- moduloBlack[path % moduloBlack.length] = true;
- }
- for (int children : parentOf.get(vertex)) {
- if (!visited[children]) {
- dfsFindBlackInCycle(children, parentOf, moduloBlack, path + 1, isBlack, visited);
- }
- }
- }
- private static void dfsCycle(ArrayList<int[]> cycleVertexAndSize, char[][] map, int x, int y, boolean[][] visited, boolean[][] onStack, ArrayDeque<int[]> stack) {
- visited[x][y] = true;
- onStack[x][y] = true;
- int[] ar = {x, y};
- stack.push(ar);
- ar = null;
- int nextX;
- int nextY;
- if (map[x][y] == 'R') {
- nextX = x;
- nextY = y + 1;
- } else if (map[x][y] == 'L') {
- nextX = x;
- nextY = y - 1;
- } else if (map[x][y] == 'U') {
- nextX = x - 1;
- nextY = y;
- } else {
- nextX = x + 1;
- nextY = y;
- }
- if (!visited[nextX][nextY]) {
- dfsCycle(cycleVertexAndSize, map, nextX ,nextY, visited, onStack, stack);
- } else {
- if (onStack[nextX][nextY]) {
- int circleSize = 1;
- while (!(stack.peek()[0] == nextX && stack.peek()[1] == nextY)) {
- stack.pop();
- circleSize++;
- }
- int[] vertexAndSize = new int[3];
- vertexAndSize[0] = nextX;
- vertexAndSize[1] = nextY;
- vertexAndSize[2] = circleSize;
- cycleVertexAndSize.add(vertexAndSize);
- vertexAndSize = null;
- }
- }
- if (!stack.isEmpty() && stack.peek()[0] == x && stack.peek()[1] == y) {
- stack.pop();
- }
- onStack[x][y] = false;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement