結果
問題 | No.13 囲みたい! |
ユーザー | mlihua09 |
提出日時 | 2020-09-21 10:38:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 132 ms / 5,000 ms |
コード長 | 2,631 bytes |
コンパイル時間 | 556 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 78,760 KB |
最終ジャッジ日時 | 2023-09-06 16:59:50 |
合計ジャッジ時間 | 3,000 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
71,628 KB |
testcase_01 | AC | 96 ms
71,336 KB |
testcase_02 | AC | 91 ms
71,372 KB |
testcase_03 | AC | 115 ms
77,800 KB |
testcase_04 | AC | 96 ms
77,252 KB |
testcase_05 | AC | 121 ms
78,692 KB |
testcase_06 | AC | 100 ms
77,000 KB |
testcase_07 | AC | 132 ms
78,760 KB |
testcase_08 | AC | 116 ms
78,080 KB |
testcase_09 | AC | 109 ms
77,944 KB |
testcase_10 | AC | 101 ms
77,184 KB |
testcase_11 | AC | 105 ms
78,208 KB |
testcase_12 | AC | 93 ms
72,232 KB |
testcase_13 | AC | 111 ms
77,380 KB |
testcase_14 | AC | 103 ms
77,480 KB |
testcase_15 | AC | 91 ms
71,632 KB |
ソースコード
W, H = map(int, input().split()) M = [list(map(int, input().split())) for i in range(H)] visited = [[0] * W + [-1] for i in range(H)] + [[-1] * (W + 1)] from collections import deque for i in range(H): for j in range(W): if visited[i][j] == 0: que = [] X = M[i][j] if visited[i + 1][j] == 0 and M[i + 1][j] == X: visited[i + 1][j] = 1 que += [i + 1, j, 0] if visited[i][j + 1] == 0 and M[i][j + 1] == X: visited[i][j + 1] = 1 que += [i, j + 1, 1] if visited[i - 1][j] == 0 and M[i - 1][j] == X: visited[i - 1][j] = 1 que += [i - 1, j, 2] if visited[i][j - 1] == 0 and M[i][j - 1] == X: visited[i][j - 1] = 1 que += [i][j - 1, 3] visited[i][j] = 1 que = deque(que) while que: x, y, q = que.popleft(), que.popleft(), que.popleft() if visited[x - 1][y] != -1 and M[x - 1][y] == X and q != 0: if visited[x - 1][y]: print('possible') exit() else: visited[x - 1][y] = 1 que.extend([x - 1, y, 2]) if visited[x + 1][y] != -1 and M[x + 1][y] == X and q != 2: if visited[x + 1][y]: print('possible') exit() else: visited[x + 1][y] = 1 que.extend([x + 1, y, 0]) if visited[x][y - 1] != -1 and M[x][y - 1] == X and q != 1: if visited[x][y - 1]: print('possible') exit() else: visited[x][y - 1] = 1 que.extend([x, y - 1, 3]) if visited[x][y + 1] != -1 and M[x][y + 1] == X and q != 3: if visited[x][y + 1]: print('possible') exit() else: visited[x][y + 1] = 1 que.extend([x, y + 1, 1]) print('impossible')