結果
問題 | No.124 門松列(3) |
ユーザー | yuki2006 |
提出日時 | 2015-01-10 17:55:08 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 266 ms / 5,000 ms |
コード長 | 3,510 bytes |
コンパイル時間 | 4,918 ms |
コンパイル使用メモリ | 82,980 KB |
実行使用メモリ | 63,092 KB |
最終ジャッジ日時 | 2023-09-03 22:56:42 |
合計ジャッジ時間 | 11,867 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 247 ms
62,440 KB |
testcase_01 | AC | 120 ms
39,996 KB |
testcase_02 | AC | 118 ms
39,292 KB |
testcase_03 | AC | 266 ms
48,820 KB |
testcase_04 | AC | 241 ms
48,816 KB |
testcase_05 | AC | 248 ms
48,704 KB |
testcase_06 | AC | 120 ms
40,048 KB |
testcase_07 | AC | 121 ms
39,400 KB |
testcase_08 | AC | 120 ms
39,732 KB |
testcase_09 | AC | 120 ms
39,272 KB |
testcase_10 | AC | 121 ms
39,936 KB |
testcase_11 | AC | 120 ms
39,656 KB |
testcase_12 | AC | 121 ms
39,188 KB |
testcase_13 | AC | 121 ms
39,804 KB |
testcase_14 | AC | 132 ms
40,528 KB |
testcase_15 | AC | 130 ms
55,804 KB |
testcase_16 | AC | 180 ms
56,892 KB |
testcase_17 | AC | 137 ms
55,764 KB |
testcase_18 | AC | 129 ms
55,876 KB |
testcase_19 | AC | 140 ms
55,984 KB |
testcase_20 | AC | 168 ms
55,840 KB |
testcase_21 | AC | 130 ms
55,920 KB |
testcase_22 | AC | 146 ms
55,980 KB |
testcase_23 | AC | 202 ms
59,752 KB |
testcase_24 | AC | 222 ms
59,164 KB |
testcase_25 | AC | 215 ms
59,716 KB |
testcase_26 | AC | 189 ms
59,060 KB |
testcase_27 | AC | 182 ms
58,692 KB |
testcase_28 | AC | 247 ms
63,092 KB |
testcase_29 | AC | 263 ms
61,660 KB |
ソースコード
import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class yukicoder123 { class Tuple { int x; int y; int[] his; Tuple(int x, int y, int[] his) { this.x = x; this.y = y; this.his = his; } boolean checkSequence(int c) { return isKadomatsuSequence(his[1], his[2], c); } @Override public String toString() { return "" + x + ":" + y + Arrays.toString(this.his); } } int[][] vec = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; boolean isKadomatsuSequence(int a, int b, int c) { if (a == c) { return false; } return (a - b) * (b - c) < 0; } int is(boolean b) { return b ? 1 : 0; } public yukicoder123() { Scanner scanner = new Scanner(System.in); int W = scanner.nextInt(); int H = scanner.nextInt(); int[][] matrix = new int[H][W]; int[][][][] checked = new int[H][W][10][2]; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { matrix[i][j] = scanner.nextInt(); for (int k = 0; k < 10; k++) { Arrays.fill(checked[i][j][k], Integer.MAX_VALUE); } } } LinkedList<Tuple> nextQueue = new LinkedList<>(); LinkedList<Tuple> queue = new LinkedList<>(); for (int i = 0; i < 10; i++) { Arrays.fill(checked[0][0][i], Integer.MAX_VALUE); } int start = matrix[0][0]; if (matrix[0][0] != matrix[0][1]) { int flag = is(matrix[0][0] > matrix[0][1]); checked[0][1][start][flag] = 1; queue.add(new Tuple(1, 0, new int[]{0, matrix[0][0], matrix[0][1]})); } if (matrix[0][0] != matrix[1][0]) { int flag = is(matrix[0][0] > matrix[1][0]); checked[1][0][start][flag] = 1; queue.add(new Tuple(0, 1, new int[]{0, matrix[0][0], matrix[1][0]})); } int turn = 2; boolean isGoal = false; MAIN: while (queue.size() > 0) { while (queue.size() > 0) { Tuple tuple = queue.pop(); for (int[] v : vec) { int x = tuple.x + v[0]; int y = tuple.y + v[1]; if (!(0 <= x && x < W && 0 <= y && y < H)) { continue; } if (!tuple.checkSequence(matrix[y][x])) { continue; } int flag = is(tuple.his[2] - matrix[y][x] > 0); if (checked[y][x][tuple.his[2]][flag] <= turn) { continue; } checked[y][x][tuple.his[2]][flag] = turn; if (y == H - 1 && x == W - 1) { isGoal = true; break MAIN; } nextQueue.add(new Tuple(x, y, new int[]{tuple.his[1], tuple.his[2], matrix[y][x]})); } } queue.addAll(nextQueue); nextQueue.clear(); turn++; } if (isGoal) { System.out.println(turn); } else { System.out.println(-1); } } public static void main(String[] args) { yukicoder123 hoge = new yukicoder123(); } }