AtCoder Beginner Contest 007 C - 幅優先探索

昨日は、解法に感心した問題をブログに書きましたが、
今日は、解説を見ても解けなかった問題を記しておきます。

解くことのできなかった問題は、
カテゴリー「負債」につっこんで、残しておくことにしました。
あとで見返して解くことができた時に、晴れてこの記事は「負債」から取り除かれます。

そして、未来の自分に宛ててるので、少し言葉遣いが雑になります。

AtCoder Beginner Contest 007 C - 幅優先探索

C - 幅優先探索

問題文があまりに長いので、引用しないからリンク先参照。

考え方

AtCoder Beginner Contest 007 解説

解説にもある通り、問題文で紹介されていた「幅優先探索」の手法をそのまま実装。

最大50マス×50マスになる迷路を、char型の二次配列[y座標][x座標]で初期化し、
それぞれの要素には、壁を表す'#'と、空きを表す'.'のどちらかが入っている。

上下左右のマスが空きマスかどうかを判定するために、
「y座標、x座標、手数」のメンバーを持つCellクラスを用意し、
Cellクラス型の一次配列でキューを作成。

キューには最初に、スタート地点の座標を持つ1つだけが格納されていて、
ゴールを見つけるまで以下のループを繰り返す。

1. popメソッドでキューの先頭のCellクラスを取り出す。
2. 取り出したCellクラスの(y , x)座標を使用して、上下左右のマスが空きマスかどうかを判定。
3. 空きマスだった場合は、そのマスの座標を持つCellクラスをキューの末尾に追加。
4. 次回以降の検索で、再びこのマスに逆戻りしないよう、現在のマスを'#'（壁マス）に変更。

提出したソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int head = 0;	// キューの先頭
	static int tail = 0;	// キューの末尾
	static Cell[] queue = new Cell[255];

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
			// 行と列の値の受け取り
			String[] RC = br.readLine().split(" ");
			int R = Integer.parseInt(RC[0]);
			int C = Integer.parseInt(RC[1]);

			// スタートマスの座標の受け取り
			String[] sysx = br.readLine().split(" ");
			int sy = Integer.parseInt(sysx[0]) - 1; // 配列は0オリジンなのでそれぞれ-1
			int sx = Integer.parseInt(sysx[1]) - 1;

			// ゴールマスの座標の受け取り
			String[] gygx = br.readLine().split(" ");
			int gy = Integer.parseInt(gygx[0]) - 1;
			int gx = Integer.parseInt(gygx[1]) - 1;

			// 迷路の内容を二次配列で保管
			char[][] labyrinth = new char[R][C];
			for (int i = 0; i < R; i++) {
				String cell = br.readLine();
				for (int j = 0; j < C; j++) {
					labyrinth[i][j] = cell.charAt(j);
				}
			}

			// 上下左右のマスが、空きマスか壁マスかを判定
			push(sy, sx, 0);
			boolean hasGoaled = false;
			int ans = -1;
			while (!hasGoaled) {
				Cell cur = pop();
				// ゴールマスを見つけられたら抜ける
				if (cur.y == gy && cur.x == gx) {
					ans = cur.cnt;
					hasGoaled = true;
				}
				// 上
				if (labyrinth[cur.y - 1][cur.x] == '.') {
					push(cur.y - 1, cur.x, cur.cnt + 1);
				}
				// 下
				if (labyrinth[cur.y + 1][cur.x] == '.') {
					push(cur.y + 1, cur.x, cur.cnt + 1);
				}
				// 左
				if (labyrinth[cur.y][cur.x - 1] == '.') {
					push(cur.y, cur.x - 1, cur.cnt + 1);
				}
				// 右
				if (labyrinth[cur.y][cur.x + 1] == '.') {
					push(cur.y, cur.x + 1, cur.cnt + 1);
				}
				// 現在のマスは、逆戻りしないように壁マスにしてしまう
				labyrinth[cur.y][cur.x] = '#';

			}
			System.out.println(ans);

		} catch (IOException e) {
			e.printStackTrace();
		}

	}

	static void push(int y, int x, int cnt) {
		if ((tail + 1) % queue.length != head) {
			queue[tail] = new Cell(y, x, cnt);
			tail = (tail + 1) % queue.length;
		} else {
			System.err.println("キューが満タンです");
		}
	}

	static Cell pop() {
		Cell ret;
		if (head != tail) {
			ret = queue[head];
			head = (head + 1) % queue.length;
		} else {
			System.err.println("キューが空っぽです");
			ret = null;
		}
		return ret;
	}

}

class Cell {
	int y;	// y座標
	int x;	// x座標
	int cnt;	// 手数

	public Cell(int y, int x, int cnt) {
		this.y = y;
		this.x = x;
		this.cnt = cnt;
	}
}

実行結果

入力例1,2のような小さな迷路は「AC」になるが、
入力例3のように広い迷路の場合、すぐにキューが満杯になってしまい「WA」になる。

なお、キューの大きさをヤケクソで「10^6」くらいにしても満杯になるし、その場合は「TLE」に変わる。
（キューはリング上にしているので、本当に中身が満タンになっている）

要するに、とんでもない量のオーダーとなってしまう……

おそらく、同じマスを色んなルートから通ることができるので、
単純に50 * 50 の容量じゃキューは足りないのだと思う。

とはいえ、実行するごとに、
空きマスは壁マスに変更されて減っていくため、サイズを10^6に取っても満杯になるのは、
そもそも引数とか変数の設定にミスがあるのかも？