やってみた。

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

package jp.noragrammer.puzzle;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.LineNumberReader;
import java.util.ArrayList;

public class Maze {
	public static void main(String args[]) throws IOException{
		Maze maze = new Maze();
		maze.start();
	}
	char maze[][];
	public void start() throws IOException{
		readFile();
		solve();
		//output();
	}
	void readFile() throws IOException{
		FileInputStream fis = new FileInputStream("maze.txt");
		InputStreamReader isr = new InputStreamReader(fis);
		LineNumberReader lnr = new LineNumberReader(isr);
		ArrayList<String> als = new ArrayList<String>();
		while ( lnr.ready()){
			als.add(lnr.readLine());
		}
		lnr.close();
		isr.close();
		fis.close();
		maze = new char[als.size()][];
		int y = 0;
		for (String line:als){
			maze[y] = new char[line.length()];
			for (int x = 0 ; x < line.length() ; x++ ){
				maze[y][x] = line.charAt(x);
			} 
			y++;
		}
	}
	public void output(){
		for (int y = 0 ; y < maze.length ; y++ ){
			for ( int x = 0 ; x < maze[y].length ; x++ ){
				System.out.print(maze[y][x]);
			}
			System.out.println();
		}
	}
	int startx,starty;
	public void solve(){
		searchStart();
		history = new ArrayList<Move>();
		solve(starty,startx,0);
	}
	ArrayList<Move> answer = null;
	ArrayList<Move> history;
	
	void searchStart(){
		for (int y = 0 ; y < maze.length ; y ++ ){
			for (int x = 0 ; x < maze[y].length ; x++ ){
				if ( maze[y][x] == 'S'){
					startx = x;
					starty = y;
					return;
				}
			}
		}
	}
	int md=1000000;
	@SuppressWarnings("unchecked")
	public void solve(int y,int x,int depth ) {
		//System.out.println("y:"+y+"x:"+x);
		//output();
		if ( maze[y][x] == 'G' ){
			if ( answer == null ){
				answer = (ArrayList<Move>) history.clone(); 
				md = depth;
			} else if ( answer.size()>history.size()){
				answer = (ArrayList<Move>) history.clone();
				md = depth;
			} else
				return;
			System.out.println("length:"+answer.size());
			output();
			System.out.println();
			return ;
		}
		if ( depth >= md ) {
			return ;
		}
		if ( maze[y][x] == ' ' ){
			maze[y][x] = '$';
			history.add(new Move(y,x));
			solve(y-1,x,depth+1);
			solve(y+1,x,depth+1);
			solve(y,x-1,depth+1);
			solve(y,x+1,depth+1);
			history.remove(history.size()-1);
			maze[y][x]= ' ' ;
		} else if ( maze[y][x] == 'S'){
			solve(y-1,x,depth+1);
			solve(y+1,x,depth+1);
			solve(y,x-1,depth+1);
			solve(y,x+1,depth+1);
		}
	}
}
package jp.noragrammer.puzzle;

public class Move {
	int y;
	int x;
	public Move(int y,int x){
		this.y = y;
		this.x = x;
	}
}