ABC 020 C: 壁抜け

解法

ゴールについた時の(歩数, 黒マスを通った回数)の組み合わせを記録しておき、それぞれについてxの最大値を求めれば良い。黒マスを通った回数は高々100なので、大した量にはならない。

コード

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	private static final int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] arg) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int T = sc.nextInt();

		char[][] map = new char[H][];
		for (int i = 0; i < H; i++) {
			map[i] = sc.next().toCharArray();
		}
		sc.close();

		int sx = -1;
		int sy = -1;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (map[i][j] == 'S') {
					sx = i;
					sy = j;
				}
			}
		}

		int[][][] dp = new int[H][W][H * W];
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				Arrays.fill(dp[i][j], 1000000000);
			}
		}
		dp[sx][sy][0] = 0;
		int max = 0;
		Deque<Integer[]> deque = new ArrayDeque<>();
		deque.addLast(new Integer[] { sx, sy, 0 });
		while (!deque.isEmpty()) {
			Integer[] poll = deque.pollFirst();
			for (int d = 0; d < dir.length; d++) {
				int x = poll[0] + dir[d][0];
				int y = poll[1] + dir[d][1];
				int i = poll[2];
				if (x < 0 || y < 0 || x >= H || y >= W) {
					continue;
				}

				if (map[x][y] == '.' && dp[x][y][i] > dp[poll[0]][poll[1]][i] + 1) {
					dp[x][y][i] = dp[poll[0]][poll[1]][i] + 1;
					if (map[x][y] == '.') {
						deque.addLast(new Integer[] { x, y, i });
					}
				} else if (map[x][y] == '#' && i + 1 < H * W && dp[x][y][i + 1] > dp[poll[0]][poll[1]][i] + 1) {
					dp[x][y][i + 1] = dp[poll[0]][poll[1]][i] + 1;
					deque.addLast(new Integer[] { x, y, i + 1 });
				} else if (map[x][y] == 'G' && dp[x][y][i] > dp[poll[0]][poll[1]][i] + 1) {
					dp[x][y][i] = dp[poll[0]][poll[1]][i] + 1;
					if (i != 0) {
						int rest = T - dp[x][y][i];
						max = Math.max(max, rest / i + 1);
					}

				}

			}
		}
		System.out.println(max);

	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}