[Algorithm] 👁️白駿10026赤薬

0、問題

赤緑の薬水はほとんど赤緑の違いを感じない.そのため、赤緑色の弱い人が見る絵とは違います.
サイズN×Nインチメッシュの各格子には、R(赤)、G(緑)、B(青)を塗った図があります.図はいくつかの領域に分けられ、領域は同じ色で構成されています.また、同じ色が上下左右に隣接している場合、2文字は同じ領域に属する.(色の違いがほとんど感じられない場合は同じ色とも呼ばれます)
たとえば、図が次のように表示されている場合.
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
赤い薬ではない人から見れば、エリアの総数は4つです.(赤2、青1、緑1)しかし赤の人は3つのエリアを見ることができます.(赤-緑2、青1)
画像が入力されると、赤と非赤の人が見る領域数を求めるプログラムを作成します.
入力
1行目はNです.(1 ≤ N ≤ 100)
2行目からN行目に1枚の図が与えられます.
しゅつりょく
赤緑色薬ではない人が見た領域数と赤緑色薬の人が見た領域数を空白に分けて出力します.

1.アイデア

💡 正常な人と赤い薬を分けて並べます
💡 赤い薬水の配列はGをRに変換します
💡 bfs接続を使用したブロックcnt

2.コア解答

正常人と赤色の薬水を別々に並べた

char[][] map = new char[n][n];
char[][] abnormalMap = new char[n][n];

赤緑色薬の配列はGをRに変換する

である.

for (int i = 0; i < n; i++) {
	String[] s = br.readLine().split("");
	for (int j = 0; j < n; j++) {
		char tmp = s[j].charAt(0);
				
		if ('G' == tmp) {
			abnormalMap[i][j] = 'R';
			continue;
		}

		abnormalMap[i][j] = tmp;
		map[i][j] = tmp;
	}
}

bfsで接続されたブロックを使用して、cntボックス

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		if (!visited[i][j]) {
			bfs(i, j, map);
			cnt[0]++;
		}
	}
}

visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		if (!visited[i][j]) {
			bfs(i, j, abnormalMap);
			cnt[1]++;
		}
	}
}

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;

public class Graph_11 {
	static boolean[][] visited;
	static int n;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int[] cnt = new int[2];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		char[][] map = new char[n][n];
		char[][] abnormalMap = new char[n][n];
		visited = new boolean[n][n];

		for (int i = 0; i < n; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < n; j++) {
				char tmp = s[j].charAt(0);
				
				if ('G' == tmp) {
					abnormalMap[i][j] = 'R';
					continue;
				}

				abnormalMap[i][j] = tmp;
				map[i][j] = tmp;
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					bfs(i, j, map);
					cnt[0]++;
				}
			}
		}

		visited = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					bfs(i, j, abnormalMap);
					cnt[1]++;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(cnt[0]);
		sb.append(" ");
		sb.append(cnt[1]);
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void bfs(int x, int y, char[][] map) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));

		while (!q.isEmpty()) {
			Node cur = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n)
					continue;

				if (!visited[nx][ny] && map[nx][ny] == map[cur.x][cur.y]) {
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				}

			}
		}
	}

	static class Node {
		int x;
		int y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}

4.結果

成功
Stringequalsで比較すると、NullpointErrorが発生し続けます.一字ならできるだけcharを使ったほうがいいです.😥