下らない内容だなぁと思い人もたくさんいるかと思いますが、
自分は今まで幅優先探索が苦手で敬遠してきました！(笑

そんなお仲間がいらっしゃればご参考になればと。
この記事はそれ以上でもそれ以下でもございません。

まず、きっかけです。
最近いろいろなところで目にしたので、是非解きたいと思った問題がありまして、、

人材獲得作戦・４　試験問題ほか | 人生を書き換える者すらいた。
http://okajima.air-nifty.com/b/2010/01/post-abc6.html

これなんですが、読んでみたら簡単そうなんですが、どうやら幅優先探索(BFS:BreadthFirstSearch)を使いそう。
TopCoderでは、「BFSがベストアンサー！」みたいな問題は今まで見かけなかったので放置していたんですが、
腹をくくって勉強。
DFSは得意なんだよね。なぜか、あの再帰具合が。

で、たまたまITMediaで連載中の講座でも探索が！
これは偶然だけども。

知れば天国、知らねば地獄――「探索」虎の巻 | 最強最速アルゴリズマー養成講座
http://www.itmedia.co.jp/enterprise/articles/1001/16/news001.html

探索は基本だよねえ。うん。

Javaでの実装に使うもの

そこを読ませて頂いても、Wikipediaの解説を読んでも、キュー(Queue)を使うのが基本らしい。
幅優先っていう概念はわかりやすいんだけどね。実装がねー

JavaでQueueだと、Queueインターフェイスを実装したLinkedListなんかがお手頃。
※ 話が逸れるけど、Eclipseで「LLi」ってとこまでいれて保管すると一番上にLinkedListがでる。

で、問題はなんのメソッドを使うか。
Stackインターフェイスも実装しているからややこしいんだけど、
Queueは先入れ先出し(FIFO)が原則なので、後方から入れて先頭から出すようにする。
行列と同じ。以下の２つのメソッドを使う。

LinkedList#offer(e)
リストの末尾に追加。

LinkedList#poll()
リストの先頭を取得して削除。

Stackに関係するメソッドは有名だから知ってたけど、
この２つは最近まで全然知らなかった。（のは俺だけかもしれない）

実装

後は書くしか無い。

ALGORITHM NOTE | 幅優先探索 Breadth First Search
http://algorithms.blog55.fc2.com/blog-entry-127.html

参考にしました。このサイトにはいつも助けられてます。

自分で分かりやすく書きたかったので、結構だらだら長いコードだけど、こんな感じ。

public class BreadthFirstSearch {
	Point[] move = new Point[]{new Point(0, -1), new Point(-1,0), new Point(1, 0), new Point(0,1)};
	char[] directions = new char[]{'r', 'd', 'u', 'l'};

	public BreadthFirstSearch(int[][] input, int sx, int sy){
		class Puzzle {
			int[][] map = new int[3][3];
			int x = 0;
			int y = 0;
			String path;

			public Puzzle(int[][] map, int x, int y, String path) {
				this.map = map;
				this.x = x;
				this.y = y;
				this.path = path;
			}

			public boolean check(){
				for (int i = 0; i < 8; i++) {
					if (this.map[i / 3][i % 3] != i+1) return false;
				}
				return true;
			}
		}

		LinkedList<Puzzle> queue = new LinkedList<Puzzle>();
		queue.push(new Puzzle(input, sx, sy, ""));

		BFS : while (queue.size() > 0) {
			Puzzle p = queue.poll();

			for (int i = 0; i < 4; i++) {
				int x = p.x + move[i].x;
				int y = p.y + move[i].y;

				if (x >= 0 && x <= 2 && y >= 0 && y <= 2) {
					int[][] map = this.dc(p.map);
					map[p.x][p.y] = map[x][y];
					map[x][y] = 0;

					Puzzle moved = new Puzzle(map, x, y, p.path + directions[i]);
					if (moved.check()) {
						System.out.println(moved.path);
						break BFS;
					}

					queue.add(moved);
				}
			}
		}

		System.out.println("#END");
	}

	public int[][] dc(int[][] input){
		int[][] output = new int[input.length][input[0].length];
		for (int i = 0; i < input.length; i++) {
			output[i] = input[i].clone();
		}
		return output;
	}

	public static void main(String[] args) throws FileNotFoundException {
		FileInputStream fis = new FileInputStream("src/study/puzzle.in");
		Scanner sc = new Scanner(fis);

		int[][] puzzle = new int[3][3];
		int x = 0;
		int y = 0;

		for (int i = 0; i < 9; i++) {
			char input = sc.next().charAt(0);
			if (input == 'x') {
				x = i / 3;
				y = i % 3;
				puzzle[i / 3][i % 3] = 0;
			} else {
				puzzle[i / 3][i % 3] = input - '0';
			}
		}

		new BreadthFirstSearch(puzzle, x, y);
	}
}

次に本命のあのサイト。
せっかくだからTopCoderっぽくコストから出してみた。
かなり回りくどいけど、書いてて自分で勉強になった。

public class Kuma4_1 {
	static final int width = 26;
	static final int height = 13;
	Point[] movable = new Point[]{new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1)};

	public Kuma4_1(char[][] map, int sx, int sy, int gx, int gy) {
		LinkedList<Point> queue = new LinkedList<Point>();
		queue.add(new Point(sx, sy));
		int cost = 1;
		int[][] costMap = new int[height][width];
		char[][] copiedMap = this.dc(map);

		BFS: while (queue.size() > 0) {
			Point now = queue.poll();

			for (int i = 0; i < movable.length; i++) {
				int x = now.x + movable[i].x;
				int y = now.y + movable[i].y;

				if (map[x][y] == 'G') {
					costMap[x][y] = cost;
					this.out(copiedMap, costMap, gx, gy);
					break BFS;

				} else if (map[x][y] == ' ') {
					costMap[x][y] = cost;
					map[x][y] = '#';
					queue.offer(new Point(x,y));
				}
			}

			cost++;
		}

		System.out.println("#process end");
	}

	public void out(char[][] map, int[][] costMap, int gx, int gy){
		int cost = costMap[gx][gy];
		Point p = new Point(gx, gy);
		while (cost > 1){
			cost--;
			for (int i = 0; i < movable.length; i++) {
				int x = p.x + movable[i].x;
				int y = p.y + movable[i].y;

				if (costMap[x][y] == cost) {
					map[x][y] = '$';
					p = new Point(x,y);
				}
			}
		}

		for (int i = 0; i < map.length; i++) {
			System.out.println(new String(map[i]));
		}
	}

	public void out(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.printf("%3d", map[i][j]);
			}
			System.out.println();
		}
	}

	public void out(char[][] map) {
		for (char i = 0; i < map.length; i++) {
			System.out.println(new String(map[i]));
		}
	}

	public char[][] dc(char[][] input){
		char[][] output = new char[input.length][input[0].length];
		for (char i = 0; i < input.length; i++) {
			output[i] = input[i].clone();
		}
		return output;
	}

	public static void main(String[] args) throws FileNotFoundException {
		FileInputStream fis = new FileInputStream("src/study/kuma4.in");
		Scanner sc = new Scanner(fis);

		char[][] map = new char[height][width];

		for (int i = 0; sc.hasNext(); i++) {
			String line = sc.nextLine();
			map[i] = line.toCharArray();
		}

		int sx=0, sy=0, gx=0, gy=0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 'S') {
					sx = i;
					sy = j;
				} else if (map[i][j] == 'G') {
					gx = i;
					gy = j;
				}
			}
		}

		new Kuma4_1(map, sx, sy, gx, gy);
	}

しかしなげぇ。でも、書く時間自体はそんなかからなかった。30分弱くらいかなあ。
でも、アルゴリズム調べてからだから、そう考えると論外だとも。

とにかく、ぼくはこれで幅優先探索をやっと覚えました！ばっちこい。