AOJ 2320: Infinity Maze

問題

Infinity Maze | Aizu Online Judge

H*Wの迷路が与えられ、ロボットをL回移動させる。ロボットは壁や障害物にぶつかると右に90度回転する。この回転は移動回数にはカウントしない。L回移動させた後、ロボットはどこにいてどこを向いているか。

解法

 1 \leq L \leq 10^{18}だが、ロボットの状態は位置が10000通り、向きが4通りで高々40000通りしかないので、必ず周期的な動きになる。1周期の移動回数を出して剰余を取れば探索可能な数になる。

コード

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int H = sc.nextInt();
			if (H == 0) {
				sc.close();
				break;
			}
			int W = sc.nextInt();
			long L = sc.nextLong();
			int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };// 北、東、南、西
			char[][] maze = new char[H][];
			for (int i = 0; i < maze.length; i++) {
				maze[i] = sc.next().toCharArray();
			}

			long[][] dp = new long[10000][4];// [位置][向き]
			int now = 0;
			int d = 0;// 向き N:0, E:1, S:2, W:3
			for (int i = 0; i < maze.length; i++) {
				for (int j = 0; j < maze[i].length; j++) {
					if (maze[i][j] != '#' && maze[i][j] != '.') {
						now = i * 100 + j;
						if (maze[i][j] == 'N') {
							d = 0;
						} else if (maze[i][j] == 'E') {
							d = 1;
						} else if (maze[i][j] == 'S') {
							d = 2;
						} else if (maze[i][j] == 'W') {
							d = 3;
						}
					}
				}
			}

			while (L > 0) {
				int x = now / 100;
				int y = now - x * 100;
				x += dir[d][0];
				y += dir[d][1];
				if (x < 0 || x >= H || y < 0 || y >= W || maze[x][y] == '#') {
					d = (d + 1) % 4;
					continue;
				}

				int next = x * 100 + y;// 次のマス
				L--;
				if (dp[next][d] == 0) {
					dp[next][d] = L;
				} else {
					long cycle = dp[next][d] - L;
					L = L % cycle;
				}

				now = next;
			}

			int x = now / 100;
			int y = now - x * 100;
			char face = '.';
			if (d == 0) {
				face = 'N';
			} else if (d == 1) {
				face = 'E';
			} else if (d == 2) {
				face = 'S';
			} else if (d == 3) {
				face = 'W';
			}

			System.out.println((x + 1) + " " + (y + 1) + " " + face);
			System.gc();
		}

	}
}