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; } }