mimizuの日記

2010-01-11

人材獲得作戦・4 試験問題

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

所要時間は問題を読み始めてから解いてみようと思い立つまでに5分、eclipseを立ち上げて書き終えるまでに20分で計25分ほど。試したのは問題文中のサンプル入出力のみだけど、さすがに単純なBFSで間違ってるってことはないでしょう。

コードの方は短時間で書くことを優先したので大分雑な感じになってます。

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;


public class Maze {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<char[]> list = new ArrayList<char[]>();
		while (sc.hasNext()) {
			list.add(sc.nextLine().toCharArray());
		}
		char[][] maze = list.toArray(new char[list.size()][]);
		int sx = 0, sy = 0;
findStart:
		for (int y = 0; y < maze.length; y++) {
			for (int x = 0; x < maze[0].length; x++) {
				if (maze[y][x] == 'S') {
					sx = x;
					sy = y;
					break findStart;
				}
			}
		}
		
		Queue<Point> queue = new ArrayDeque<Point>();
		queue.add(new Point(sx, sy));
		
		Point[][] route = new Point[maze.length][maze[0].length];
		int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
bfs:
		while (!queue.isEmpty()) {
			Point p = queue.poll();
			for (int i = 0; i < dx.length; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				if (maze[ny][nx] == ' ') {
					maze[ny][nx] = '_';
					queue.add(new Point(nx, ny));
					route[ny][nx] = p;
				}
				else if (maze[ny][nx] == 'G') {
					while (p != null) {
						maze[p.y][p.x] = '$';
						p = route[p.y][p.x];
					}
					break bfs;
				}
			}
		}
		
		maze[sy][sx] = 'S';
		for (int y = 0; y < maze.length; y++) {
			for (int x = 0; x < maze[0].length; x++) {
				if (maze[y][x] == '_') {
					maze[y][x] = ' ';
				}
			}
		}
		
		for (int y = 0; y < maze.length; y++) {
			System.out.println(maze[y]);
		}
	}

}