迷路探索メソッド

迷路を探索するメソッド。
幅優先探索が分からなかったので、Listを使ってそれっぽく作ってみた。
以下のような問題で利用できる。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder
D: Grid Repainting - AtCoder Beginner Contest 088 | AtCoder

【最短歩数を返すメソッド】

static int SearchRoute (int sx, int sy, int gx, int gy, String[][] ar) {
	Deque<Point> p = new ArrayDeque<>();
	p.add(new Point(sx,sy));
	int moves = 0;
	ar[sx][sy] = "0";
	int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	int s,i,j;
	while (true) {
		s = p.size();
		for (int k=0; k<s; k++) {
			i = p.getFirst().x;
			j = p.removeFirst().y;
			for (int a=0; a<4; a++) {
				if (i+dx[a]<0 || ar.length-1<i+dx[a] || j+dy[a]<0 || ar[0].length-1<j+dy[a]) {
					continue;
				}
				if (ar[i+dx[a]][j+dy[a]].equals(".")==false) {continue;}
				ar[i+dx[a]][j+dy[a]] = String.valueOf(moves+1);
				p.addLast(new Point(i+dx[a],j+dy[a]));
			}
		}
		moves++;
		if (s == 0) {break;}
	}
	if (ar[gx][gy].equals(".")) {return -1;}
	return Integer.parseInt(ar[gx][gy]);
}

スタート地点（sx,sy）、ゴール地点（gx,gy）と、"."と"#"から構成された二次元配列の迷路を引数として与えてあげることで、最短歩数が戻り値として返される。ゴール地点にたどりつけないような迷路の場合は-1が返される。

スタート地点とゴール地点の距離を求めたい場合は、戻り値に1足せばOK。

【最短ルートを描くメソッド】

static void PrintRoute (int sx, int sy, int gx, int gy, String[][] ar) {
	Deque<Integer> x = new ArrayDeque<>();
	Deque<Integer> y = new ArrayDeque<>();
	x.addFirst(sx);
	y.addFirst(sy);
	int moves = 0;
	ar[sx][sy] = "0";
	while (true) {
		int s = x.size();
		for (int k=0; k<s; k++) {
			int i = x.removeFirst();
			int j = y.removeFirst();
			if (i>0 && ar[i-1][j].equals(".")) {
				ar[i-1][j] = String.valueOf(moves+1);
				x.addLast(i-1);
				y.addLast(j);
			}
			if (i<ar.length-1 && ar[i+1][j].equals(".")) {
				ar[i+1][j] = String.valueOf(moves+1);
				x.addLast(i+1);
				y.addLast(j);
			}
			if (j>0 && ar[i][j-1].equals(".")) {
				ar[i][j-1] = String.valueOf(moves+1);
				x.addLast(i);
				y.addLast(j-1);
			}
			if (j<ar[0].length-1 && ar[i][j+1].equals(".")) {
				ar[i][j+1] = String.valueOf(moves+1);
				x.addLast(i);
				y.addLast(j+1);
			}
		}
		moves++;
		if (s == 0) {break;}
	}
	if (ar[gx][gy].equals(".")) {System.out.println("error");}
	else {
		int i = gx;
		int j = gy;
		int num = Integer.parseInt(ar[gx][gy])-1;
		while (true) {
			String s = String.valueOf(num);
				if (i>0 && ar[i-1][j].equals(s)) {
					if (Integer.parseInt(ar[i-1][j]) == num) {
						ar[i-1][j] = "$";
						i--;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (i<ar.length-1 && ar[i+1][j].equals(s)) {
					if (Integer.parseInt(ar[i+1][j]) == num) {
						ar[i+1][j] = "$";
						i++;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (j>0 && ar[i][j-1].equals(s)) {
					if (Integer.parseInt(ar[i][j-1]) == num) {
						ar[i][j-1] = "$";
						j--;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (j<ar[0].length-1 && ar[i][j+1].equals(s)) {
					if (Integer.parseInt(ar[i][j+1]) == num) {
						ar[i][j+1] = "$";
						j++;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
		}
		ar[gx][gy] = "G";
		ar[sx][sy] = "S";
		for (int a=0; a<ar.length; a++) {
			for (int b=0; b<ar[0].length; b++) {
				if (ar[a][b].matches("[#$GS]")==false) {
					System.out.print(".");
				}
				else {
					System.out.print(ar[a][b]);
				}
			}
			System.out.println();
		}
	}
}

使用例（数字は上から、迷路のサイズ（縦横）、スタート座標、ゴール座標）