Javaで迷路を幅優先探索（ゴールまでの道のりを表示する）

前回の記事の続きです。

jpliterature.hatenablog.com

前回は、スタート地点から各地点までの歩数を求め、それを int型配列moves に格納しました。

今回は moves をもとに、スタート地点からゴール地点までの道のりを表示してみたいと思います。

実装方針

・S、G、矢印の3つによって道のりを表示する（下図）

#	#	#	#	#
#	↓	←	←	#
#	↓	#	↑	#
#	G	#	S	#
#	#	#	#	#

道のりを表示するにあたっては、moves の値を頼りにスタートからゴールまで辿りながら、矢印を描いていくのがよさそうです。

しかし、スタートからゴールへとたどる場合、プログラムは分かれ道を判別することができません。

以下の画像は

・C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder

の入力例2を幅優先探索で探索したあとの moves の中身ですが、

スタート地点（00）の隣には 01 が2つあります。このうちどちらの 01 をたどればゴールに辿り着けるのかは、プログラムは実際に最後まで辿ってみないとわかりません。
これが、分かれ道を判別できないと述べた理由です。

一方、ゴールからスタートに向かう場合は、その道のりがただ1つに定まります。
上の画像でいうと、ゴール（11）の隣にある 10 、10 の隣にある 09 とたどっていけば、必ずスタート地点に辿り着くことができます。

これらのことを踏まえた上で、実際に私が書いたコードが以下になります。

import java.util.*;

void solve () {

	//入力を受け取る
	int h = nextInt(), w = nextInt();
	int sy = nextInt()-1, sx = nextInt()-1, gy = nextInt()-1, gx = nextInt()-1;
	Point start = new Point(sx, sy), goal = new Point(gx, gy);
	char[][] map = nextChar2DArray(h, w, false);

	//道のり表示用の配列に、迷路を複写しておく
	char[][] route = new char[h][w];
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			if (map[i][j] == '.') route[i][j] = '・';
			else route[i][j] = '＃';
		}
	}

	//Queueを用意し、スタート地点を入れる
	ArrayDeque<Point> dq = new ArrayDeque<>();
	dq.add(start);

	//各地点のスタート地点からの歩数を記録する二次元配列
	int[][] moves = new int[h][w];
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) moves[i][j] = -1; //-1で初期化する
	}

	//スタート地点を"#"で埋めて、探索済みにする
	map[start.getY()][start.getX()] = '#';

	//幅優先探索
	while (dq.size() > 0) {
		Point p = dq.removeFirst();
		for (int i=0; i<4; i++) {
			int x = p.getX()+D4[i].getX();
			int y = p.getY()+D4[i].getY();
			if (map[y][x] == '.') {
				dq.addLast(new Point(x, y));
				map[y][x] = '#';
				moves[y][x] = moves[p.getY()][p.getX()] + 1;
			}
		}
	}

	//道のり表示用の配列に、SとGを追加する
	route[start.getY()][start.getX()] = 'Ｓ';
	route[goal.getY()][goal.getX()] = 'Ｇ';



	//ゴールから逆算しながら、道のり表示用の配列に矢印を入れていく
	int x = goal.getX(), y = goal.getY();
	for (int i=moves[goal.getY()][goal.getX()]; i>0; i--) {
		for (int j=0; j<4; j++) {
			int tempX = x+D4[j].getX();
			int tempY = y+D4[j].getY();
			if (moves[tempY][tempX] == i-1) {
				x = tempX;
				y = tempY;
				route[y][x] = j==0? '↓' : j==1? '←' : j==2? '↑' : '→';
				break;
			}
		}
	}


	//道のり表示用配列を出力する
	printChar2DArray(route);

}

入力例2のスタートからゴールまでの道のりがどのように表示されるか、出力を見てみます。

スタートからゴールまでの道のりをキチンと表示できていますね。

このプログラムのメイン部分は「矢印をどこにどの向きで入れるか」という処理になっています。
最後に、この処理の詳細をサンプルを使ってわかりやすくシミュレーションしてみたいと思います。

03	02
00	01

左上がゴールで左下がスタートとします。ゴールから逆算するので、03 から始めます。

・03 の四方を探索して、03 より 1 少なくなっているようなマスを探す。
・そのようなマスが 03 の右側にあれば "←"、左側にあれば "→" というふうに、発見した位置とは逆の矢印を道のり表示用の配列に詰める

という処理を繰り返していくことで、スタートからゴールまでの道のりに矢印を描くことができます。

今回、このようなプログラムを作ってみて、普段の競プロとはまた違う楽しさを味わうことができました。競プロの問題だけでなく、このような視覚的に面白いプログラムを作ってみるのも、たまには面白いですね。