結果
問題 | No.13 囲みたい! |
ユーザー | uafr_cs |
提出日時 | 2017-10-30 17:29:36 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 270 ms / 5,000 ms |
コード長 | 1,725 bytes |
コンパイル時間 | 2,523 ms |
コンパイル使用メモリ | 77,260 KB |
実行使用メモリ | 47,372 KB |
最終ジャッジ日時 | 2024-05-02 01:26:21 |
合計ジャッジ時間 | 7,029 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 120 ms
40,132 KB |
testcase_01 | AC | 135 ms
41,192 KB |
testcase_02 | AC | 134 ms
41,080 KB |
testcase_03 | AC | 255 ms
47,016 KB |
testcase_04 | AC | 245 ms
47,372 KB |
testcase_05 | AC | 259 ms
46,496 KB |
testcase_06 | AC | 250 ms
46,096 KB |
testcase_07 | AC | 255 ms
46,216 KB |
testcase_08 | AC | 267 ms
46,328 KB |
testcase_09 | AC | 270 ms
46,412 KB |
testcase_10 | AC | 210 ms
42,944 KB |
testcase_11 | AC | 268 ms
45,764 KB |
testcase_12 | AC | 194 ms
42,204 KB |
testcase_13 | AC | 219 ms
44,192 KB |
testcase_14 | AC | 233 ms
44,408 KB |
testcase_15 | AC | 142 ms
41,188 KB |
ソースコード
import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { public static final int UNVISITED = 0; public static final int VISITING = 1; public static final int VISITED = 2; public static final int[][] move_dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public static boolean in_range(int x, int y, int W, int H){ return 0 <= x && x < W && 0 <= y && y < H; } public static boolean dfs(int x, int y, int px, int py, int H, int W, int[][] board, int[][] visited){ //System.out.println(y + " " + x + " " + board[y][x]); visited[y][x] = VISITING; for(final int[] move : move_dirs){ final int nx = x + move[0]; final int ny = y + move[1]; if(!in_range(nx, ny, W, H)){ continue; } if(board[y][x] != board[ny][nx]){ continue; } if(ny == py && nx == px){ continue; } if(visited[ny][nx] == UNVISITED){ if(dfs(nx, ny, x, y, H, W, board, visited)){ visited[y][x] = VISITED; return true; } }else if(visited[ny][nx] == VISITING){ visited[y][x] = VISITED; return true; } } visited[y][x] = VISITED; return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int W = sc.nextInt(); final int H = sc.nextInt(); int[][] board = new int[H][W]; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ board[i][j] = sc.nextInt(); } } int[][] visited = new int[H][W]; for(int y = 0; y < H; y++){ for(int x = 0; x < W; x++){ if(visited[y][x] != UNVISITED){ continue; } if(dfs(x, y, -1, -1, H, W, board, visited)){ System.out.println("possible"); return; } } } System.out.println("impossible"); } }