迷路の最短路

迷路の最短路(プログラミングコンテストチャレンジブック p37)

大きさN×Mの迷路が与えられる。'#','.','S','G'はそれぞれ、壁、通路、スタート、ゴールを示す。1ターンに4近傍の通路に移動できる。スタートからゴールまで移動するのに必要なターン数を求める。
制約

アルゴリズム

幅優先探索(BFS:Breadth-First Search)を使って、同じ状態には1度しか通らないようにする。一番最初にゴールにたどり着いたときのターン数が最小のターン数になる。
求めるものが、最小ターンなのでLake Counting(PKU No.2386)のようなDFSだと駄目。
DFSのときはスタックを、BFSのときはキューを使うことになる。

コード

import java.util.*;
public class shortest_path_of_labyrinth {
	static Scanner scanner;
	static Pos[] diff;
	char[][] map;
	Queue<Pos> q;
	Pos start,goal;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		// 4近傍の方向ベクトル初期化
		diff = new Pos[]{ new Pos(-1,0), new Pos(0,-1), new Pos(1,0), new Pos(0,1) };
		new shortest_path_of_labyrinth();
	}
	shortest_path_of_labyrinth(){
		int N = scanner.nextInt();
		int M = scanner.nextInt();
		map = new char[N+2][M+2];
		//周りを#で埋めて番兵的に使う
		for(int i=0; i < N+2; i++){
			if( i==0 || i==N+1 ) Arrays.fill(map[i], '#');
			else{
				String line = scanner.next();
				line = "#" + line + "#";
				int idx;
				if( (idx=line.indexOf('S')) >= 0 ) start = new Pos(i,idx,0); //スタート地点記録 ※0ターン目に到達可能
				if( (idx=line.indexOf('G')) >= 0 ) goal = new Pos(i,idx); //ゴール地点記録
				map[i] = line.toCharArray();
			}
		}
		System.out.println( solve() );
	}
	
	int solve(){
		q = new LinkedList<Pos>();
		return BFS();
	}
	int BFS(){
		q.offer( start );
		map[goal.y][goal.x] = '.'; //ゴール地点を移動可能なマス'.'に変えている。
		Pos p;
		while( (p = q.poll()) != null ){
			if( p.isEqual_Pos(goal) ) return p.count; //ゴール
			for(int i = 0; i < 4; i++){ //4近傍をキューに追加
				if( map[ p.y + diff[i].y ][ p.x + diff[i].x ] == '.'){
					map[ p.y + diff[i].y ][ p.x + diff[i].x ] = '#'; //移動不可能なマス'#'に変える(同じマスを再度訪問しないようにしている)
					q.offer( new Pos( p.y + diff[i].y, p.x+diff[i].x, p.count+1 ) );
				}
			}
		}
		return -1; //失敗
	}
}

class Pos{
	int x,y,count; //map[y][x]へターン数(count)で到達可能であることを示す。
	Pos(int y, int x){ this.y = y; this.x = x; this.count = -1; }
	Pos(int y, int x, int count){ this.y = y; this.x = x; this.count = count; }
	boolean isEqual_Pos(Pos b){ return (x == b.x && y == b.y); } //xとyだけで比較
}