gistfile1.java

import java.io.*;
import java.util.*;

public class test
{
	public static void main(String[] args) throws Exception
	{
		Board.buildBoard(args[0]).printAnswer();
	}

	static class Board
	{
		private Point[][] points;

		private Board(Point[][] points)
		{
			this.points = points;
		}

		public static Board buildBoard(String fileName) throws IOException
		{
			BufferedReader br = null;

			List<Point[]> buildResult = new ArrayList<Point[]>();
			try
			{
				br = new BufferedReader(new FileReader(fileName));

				int y = 0;
				String buf = null;
				while((buf = br.readLine()) != null)
				{
					Point[] line = new Point[buf.length()];

					for(int i=0; i<buf.length(); i++)
					{
						char ch = buf.charAt(i);
						boolean bStart = ch == 'S';
						boolean bGoal = ch == 'G';
						boolean bWall = ch == '*';

						line[i] = new Point(i, y, bStart, bGoal, bWall);
					}

					buildResult.add(line);
					y++;
				}

				// List to Array
				Point[][] buildResultArray = buildResult.toArray(new Point[0][0]);
				return new Board(buildResultArray);
			}
			finally
			{
				if(br != null)
				{
					br.close();
				}
			}
		}

		public Point getNextPoint(Point point, int moveX, int moveY)
		{
			int x = point.getX() + moveX;
			int y = point.getY() + moveY;

			if(x < 0 || x > getBoardWidth() - 1)
			{
				return null;
			}
			else if(y < 0 || y > getBoardHeight() - 1)
			{
				return null;
			}
			else
			{
				return points[y][x];
			}
		}

		public Point[] getAvailablePoints(Point currentPoint)
		{
			List<Point> availablePoints = new ArrayList<Point>();

			// 東西南北
			int[][] patterns = {
				{1, 0}, {-1, 0}, {0, 1}, {0, -1}
			};
			for(int[] pattern : patterns)
			{
				int moveX = pattern[0];
				int moveY = pattern[1];

				Point point = getNextPoint(currentPoint, moveX, moveY);
				if(isAvailable(currentPoint, point))
				{
					availablePoints.add(point);
				}
			}

			Point[] result = availablePoints.toArray(new Point[0]);
			return result;
		}

		private boolean isAvailable(Point currentPoint, Point nextPoint)
		{
			return (nextPoint != null && !nextPoint.isWall() && !nextPoint.isStart() && (nextPoint.getCost() == 0 || nextPoint.getCost() > currentPoint.getCost()));
		}

		public int getBoardWidth()
		{
			return points[0].length;
		}

		public int getBoardHeight()
		{
			return points.length;
		}

		public void printAnswer()
		{
			// スタート地点を取得する
			Point startPoint = getStartPoint();

			// 各マスのスタート地点からのコストを計算する
			calcCosts(startPoint);

			// 最短経路を検索する
			Stack<Point> route = searchRoute(startPoint);

			// 最短経路を表示する
			printRoute(route);
		}

		private Stack<Point> searchRoute(Point point)
		{
			Point[] availablePoints = getAvailablePoints(point);

			for(Point p : availablePoints)
			{
				if(p.getCost() < point.getCost())
				{
					continue;
				}

				if(p.isGoal())
				{
					// ゴール
					Stack<Point> route = new Stack<Point>();
					route.push(point);
					return route;
				}
				else
				{
					Stack<Point> route = searchRoute(p);
					if(route == null)
					{
						// 探索した結果行き止まりだった
						continue;
					}
					else
					{
						// ゴールでも行き止まりでもない（通路）
						route.push(point);
						return route;
					}
				}
			}

			// 行き場所がない＝行き止まり
			return null;
		}

		private void calcCosts(Point startPoint)
		{
			// スタート地点から移動可能なポイントのコストを計算する
			List<Point> points = calcPointCosts(startPoint);

			// 移動可能なポイントが無くなるまでコストを計算する
			while(points.size() > 0)
			{
				List<Point> nextPointList = new ArrayList<Point>();
				for(Point p : points)
				{
					List<Point> nextPoints = calcPointCosts(p);
					for(Point np : nextPoints)
					{
						nextPointList.add(np);
					}
				}

				points = nextPointList;
			}
		}

		/**
		 *	ある地点から移動可能なポイントのコストを計算し、移動可能なポイントの一覧を返却する
		 */
		private List<Point> calcPointCosts(Point point)
		{
			// 次にコスト計算可能なポイント
			List<Point> nextPoints = new ArrayList<Point>();

			// 移動可能なポイント一覧を取得する
			Point[] availablePoints = getAvailablePoints(point);

			// 行き止まり判定
			if(availablePoints.length == 0)
			{
				return nextPoints;
			}

			// コスト計算
			for(Point availablePoint : availablePoints)
			{
				int newCost = point.getCost() + 1;
				if(availablePoint.getCost() == 0)
				{
					// コスト未計算
					availablePoint.setCost(newCost);
					nextPoints.add(availablePoint);
				}
				else
				{
					// コスト計算済
					if(availablePoint.getCost() > newCost)
					{
						availablePoint.setCost(newCost);
					}
				}
			}

			return nextPoints;
		}

		public Point getStartPoint()
		{
			for(int i=0; i<points.length; i++)
			{
				for(int j=0; j<points[i].length; j++)
				{
					if(points[i][j].isStart())
					{
						return points[i][j];
					}
				}
			}

			throw new RuntimeException("Start Point is not found.");
		}

		public void printRoute(Stack<Point> route)
		{
			for(int i=0; i<points.length; i++)
			{
				for(int j=0; j<points[i].length; j++)
				{
					boolean isRoute = route.search(points[i][j]) != -1;
					System.out.print(points[i][j].toRoute(isRoute));
				}
				System.out.println();
			}
		}
	}

	static class Point
	{
		private boolean bStart;
		private boolean bGoal;
		private boolean bWall;

		private int x;
		private int y;
		private int cost;

		public Point(int x, int y, boolean bStart, boolean bGoal, boolean bWall)
		{
			this.x = x;
			this.y = y;
			this.cost = 0;
			this.bStart = bStart;
			this.bGoal = bGoal;
			this.bWall = bWall;
		}

		public int getX()
		{
			return x;
		}

		public int getY()
		{
			return y;
		}

		public boolean isStart()
		{
			return bStart;
		}

		public boolean isGoal()
		{
			return bGoal;
		}

		public boolean isWall()
		{
			return bWall;
		}

		public int getCost()
		{
			return cost;
		}

		public void setCost(int cost)
		{
			this.cost = cost;
		}

		public String toRoute(boolean isRoute)
		{
			String result = "";
			if(bStart)
			{
				result += "S";
			}
			else if(bGoal)
			{
				result += "G";
			}
			else if(bWall)
			{
				result += "*";
			}
			else if(isRoute)
			{
				result += "$";
			}
			else
			{
				result += " ";
			}

			return result;
		}
	}
}