幅優先探索 迷路を解く

迷路を解くときに使うアルゴリズムは複数ありますが、
今回は幅優先探索を用いて、迷路を解く学習をしました。
(主に友達から聞いて。)

大きく分けて、深さ優先探索と幅優先探索がありますが、
幅優先探索の場合は迷路を解くのと同時に、最短経路のステップを知ることもできるアルゴリズムです。

sample input

11 10
##.######.#
#......#..#
#.#.##.##.#
#.#........
###.##.####
#....#....#
#.#######.#
#....#.....
#.####.###.
#....#....#

sample output

-1   0   1  -1  -1  -1  -1  -1  -1  14  -1  
-1   1   2   3   4   5   6  -1  14  13  -1  
-1   2  -1   4  -1  -1   7  -1  -1  12  -1  
-1   3  -1   5   6   7   8   9  10  11  12  
-1  -1  -1   6  -1  -1   9  -1  -1  -1  -1  
-1   9   8   7   8  -1  10  11  12  13  -1  
-1  10  -1  -1  -1  -1  -1  -1  -1  14  -1  
-1  11  12  13  14  -1  18  17  16  15  16  
-1  12  -1  -1  -1  -1  19  -1  -1  -1  17  
-1  13  14  15  16  -1  20  21  22  -1  -1  
min = 22

以下がjavaで書いたプログラムコードになります。
スタート位置とゴール位置、壁の文字についてはプログラム中で記載しています。

package jp.sonoshou;

import java.io.InputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class labyrinth {
	static Scanner scanner;
	char[][] map;	//マップを格納する配列。
	int[][] dist; //スタートからの距離の配列。
	int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};	//右(1,0),下(0,1),左(-1,0),上(0,-1)の順で探索。
	
	//スキャナ用変数
	String n;
	
	//マップの大きさを定義。
	int MaxMapHeight;
	int MaxMapWidth;
	
	//スタートの位置
	int StartX = 1;
	int StartY = 0;
	
	//ゴールの位置
	int GoalX = 8;
	int GoalY = 9;
	
	//壁の文字
	char wall = '#';
	
	public labyrinth() {
		
		//マップサイズを取得。　幅　高さ　の順。
		n = scanner.next();
		MaxMapWidth = Integer.parseInt(n);
		n = scanner.next();
		MaxMapHeight = Integer.parseInt(n);
	
		//マップを配列で作成。
		map = new char[MaxMapHeight][MaxMapWidth];
		dist = new int[MaxMapHeight][MaxMapWidth];
	
		//マップを取得。
		for(int i = 0; i < MaxMapHeight; i++) {
			n = scanner.next();
			for(int j = 0; j < MaxMapWidth; j++) {
				map[i][j] = n.charAt(j);
			}
		}
		
		//スタートまでの距離を検索。
		for (int i = 0; i < MaxMapHeight; i++) {
			for (int j = 0; j < MaxMapWidth; j++) {
				dist[i][j] = -1;
			}
		}
		
		
		//幅探索初期化
		Queue<labyrinth.Point> que = new LinkedList<labyrinth.Point>();
		
		Point Start = new Point(StartY,StartX);
		Point Goal = new Point(GoalY,GoalX);	
		int tempX, tempY;
		
		//スタートの座標を代入。スタートの距離は0。
		que.offer(Start);
		dist[Start.Y][Start.X] = 0;
		
		//探索開始
		while(que.size() > 0) {
			Point point = que.poll();
			if(point.Y == Goal.Y && point.X == Goal.X) break; 
			for(int i = 0; i < 4; i++) {
				tempY = point.Y + dy[i];
				tempX = point.X + dx[i];
				
				if((0 <= tempY && tempY < MaxMapHeight) && (0 <= tempX && tempX < MaxMapWidth) 
						&& (map[tempY][tempX] != wall) && dist[tempY][tempX] == -1) {
					que.offer(new Point(tempY, tempX));
					dist[tempY][tempX] = dist[point.Y][point.X] + 1; 
				}
				
			}
		}
		
		//スタートからの距離を格納したdist配列を出力。
		for (int i = 0; i < MaxMapHeight; i++) {
			for (int j = 0; j < MaxMapWidth; j++) {
				System.out.printf("%4s",dist[i][j]+"  ");
			}
			System.out.println();
		}
		
		//スタートからゴールまでの距離を出力。
		System.out.println("min = " + dist[Goal.Y][Goal.X]);
		
	}
	
	public static void main(String[] args)throws Exception{
		InputStream in = System.in;

		//スキャナの初期化
		scanner = new Scanner(in);
		new labyrinth();
	}
	
	//ポインタクラス。迷路の座標を保持する。
	class Point {
		public int Y, X;
		
		public Point(int Y, int X) {
			this.Y = Y;
			this.X = X;
		} 
	}
	
}