結果
問題 | No.124 門松列(3) |
ユーザー | yuki2006 |
提出日時 | 2015-01-10 16:24:28 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,346 bytes |
コンパイル時間 | 6,213 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 45,272 KB |
最終ジャッジ日時 | 2023-09-03 22:55:58 |
合計ジャッジ時間 | 11,738 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 239 ms
44,892 KB |
testcase_01 | WA | - |
testcase_02 | AC | 124 ms
39,284 KB |
testcase_03 | AC | 259 ms
45,272 KB |
testcase_04 | AC | 243 ms
44,524 KB |
testcase_05 | AC | 244 ms
44,788 KB |
testcase_06 | AC | 124 ms
39,216 KB |
testcase_07 | AC | 125 ms
39,864 KB |
testcase_08 | AC | 124 ms
39,228 KB |
testcase_09 | AC | 124 ms
39,444 KB |
testcase_10 | AC | 124 ms
39,384 KB |
testcase_11 | AC | 122 ms
39,572 KB |
testcase_12 | AC | 124 ms
39,436 KB |
testcase_13 | WA | - |
testcase_14 | AC | 132 ms
40,436 KB |
testcase_15 | AC | 131 ms
39,736 KB |
testcase_16 | AC | 184 ms
40,752 KB |
testcase_17 | AC | 140 ms
39,744 KB |
testcase_18 | AC | 132 ms
39,408 KB |
testcase_19 | AC | 139 ms
39,804 KB |
testcase_20 | AC | 174 ms
39,928 KB |
testcase_21 | AC | 154 ms
39,316 KB |
testcase_22 | AC | 148 ms
39,640 KB |
testcase_23 | AC | 207 ms
43,584 KB |
testcase_24 | AC | 216 ms
44,104 KB |
testcase_25 | AC | 215 ms
44,000 KB |
testcase_26 | AC | 201 ms
41,776 KB |
testcase_27 | AC | 187 ms
41,880 KB |
testcase_28 | AC | 238 ms
44,960 KB |
testcase_29 | AC | 237 ms
45,012 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][2]; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { matrix[i][j] = scanner.nextInt(); Arrays.fill(checked[i][j], Integer.MAX_VALUE); } } LinkedList<Tuple> nextQueue = new LinkedList<>(); LinkedList<Tuple> queue = new LinkedList<>(); checked[0][0][0] = 0; checked[0][0][1] = 0; if (matrix[0][0] != matrix[0][1]) { int index = is(matrix[0][0] > matrix[0][1]); checked[0][1][index] = 1; queue.add(new Tuple(1, 0, new int[]{0, matrix[0][0], matrix[0][1]})); } if (matrix[0][0] != matrix[1][0]) { int index = is(matrix[0][0] > matrix[1][0]); checked[1][0][index] = 1; queue.add(new Tuple(0, 1, new int[]{0, matrix[0][0], matrix[1][0]})); } int turn = 2; 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][flag] <= turn) { continue; } checked[y][x][flag] = turn; if (y == H - 1 && x == W - 1) { 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++; } int result = Math.min(checked[H - 1][W - 1][0], checked[H - 1][W - 1][1]); if (result != Integer.MAX_VALUE) { System.out.println(result); } else { System.out.println(-1); } } public static void main(String[] args) { yukicoder123 hoge = new yukicoder123(); } }