結果
問題 | No.13 囲みたい! |
ユーザー | dango |
提出日時 | 2023-07-08 09:30:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 134 ms / 5,000 ms |
コード長 | 1,136 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 84,204 KB |
最終ジャッジ日時 | 2023-09-29 10:46:33 |
合計ジャッジ時間 | 2,608 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 70 ms
71,316 KB |
testcase_01 | AC | 70 ms
71,344 KB |
testcase_02 | AC | 70 ms
71,304 KB |
testcase_03 | AC | 109 ms
84,204 KB |
testcase_04 | AC | 79 ms
76,576 KB |
testcase_05 | AC | 134 ms
82,976 KB |
testcase_06 | AC | 82 ms
76,968 KB |
testcase_07 | AC | 103 ms
78,116 KB |
testcase_08 | AC | 90 ms
77,052 KB |
testcase_09 | AC | 88 ms
77,156 KB |
testcase_10 | AC | 90 ms
76,492 KB |
testcase_11 | AC | 90 ms
77,180 KB |
testcase_12 | AC | 78 ms
75,624 KB |
testcase_13 | AC | 88 ms
76,608 KB |
testcase_14 | AC | 99 ms
78,440 KB |
testcase_15 | AC | 74 ms
71,320 KB |
ソースコード
import sys sys.setrecursionlimit(15 * 10 ** 7) def POS(i, j, w): return i * (w + 2) + j def dfs(x, y, dir, number, board, w, h): dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] board[POS(x, y, w)] = -number for k in range(4): if dir == k: continue nx = x + dx[k] ny = y + dy[k] if board[POS(nx, ny, w)] == -number: return 1 if board[POS(nx, ny, w)] == number: t = dfs(nx, ny, (k + 2) % 4, number, board, w, h) if t == 1: return 1 return 0 def main(): w, h = map(int,input().split()) board = [0] * ((w + 2) * (h + 2)) for i in range(1, h + 1): row = list(map(int, input().split())) for j in range(1, w + 1): board[POS(i, j, w)] = row[j - 1] for i in range(1,h + 1): for j in range(1,w + 1): if board[POS(i, j, w)] > 0: res = dfs(i, j, 4, board[POS(i, j, w)], board, w, h) if res == 1: print("possible") exit(0) print("impossible") return if __name__ == "__main__": main()