結果
問題 | No.13 囲みたい! |
ユーザー | yuki2006 |
提出日時 | 2015-02-03 01:45:23 |
言語 | Java21 (openjdk 21) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,764 bytes |
コンパイル時間 | 3,981 ms |
コンパイル使用メモリ | 76,080 KB |
実行使用メモリ | 60,856 KB |
最終ジャッジ日時 | 2023-09-05 11:14:17 |
合計ジャッジ時間 | 6,799 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 125 ms
56,288 KB |
testcase_01 | AC | 131 ms
55,900 KB |
testcase_02 | AC | 127 ms
55,840 KB |
testcase_03 | AC | 259 ms
60,108 KB |
testcase_04 | AC | 236 ms
60,432 KB |
testcase_05 | AC | 258 ms
60,744 KB |
testcase_06 | AC | 234 ms
60,020 KB |
testcase_07 | AC | 245 ms
60,108 KB |
testcase_08 | AC | 256 ms
60,756 KB |
testcase_09 | AC | 256 ms
60,316 KB |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
ソースコード
import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Main { public static final String IMPOSSIBLE = "impossible"; public static final String POSSIBLE = "possible"; int W; int H; int[][] matrix; int[][] visited; //クラスを使わずにしてみたかったので int getPos(int i, int j) { return j * W + i; } void input() { Scanner scanner = new Scanner(System.in); //番兵を含む W = scanner.nextInt() + 2; H = scanner.nextInt() + 2; matrix = new int[H][W]; for (int i = 1; i < H-1 ; i++) { for (int j = 1; j < W-1; j++) { matrix[i][j] = scanner.nextInt(); } } } public Main() { input(); visited = new int[H][W]; for (int i = 0; i < H; i++) { Arrays.fill(visited[i], -1); } for (int i = 1; i < H - 1; i++) { for (int j = 1; j < W - 1; j++) { if (visited[i][j] != -1) { continue; } if (bfs(i, j)) { System.out.println(POSSIBLE); return; } } } System.out.println(IMPOSSIBLE); } private boolean bfs(int startX, int startY) { LinkedList<Integer> queue = new LinkedList<Integer>(); queue.add(getPos(startX, startY)); int currentNum = matrix[startX][startY]; visited[startX][startY] = 0; while (queue.size() > 0) { final Integer next = queue.pop(); int x = next % W; int y = next / W; for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { int p1 = x + i; int p2 = y + j; if (Math.abs(i + j) == 1 && matrix[p1][p2] == currentNum) { //次の場所が別の親になっているかどうかをチェックします。 if (visited[p1][p2] == 0 || visited[x][y] == getPos(p1, p2)) { continue; } if (visited[p1][p2] != -1) { //この時点で囲める return true; } //次の場所の親が元の場所と設定します。 visited[p1][p2] = getPos(x, y); queue.add(getPos(p1, p2)); } } } } return false; } public static void main(String[] args) { new Main(); }}