結果
問題 | No.2412 YOU Grow Bigger! |
ユーザー |
|
提出日時 | 2024-12-03 00:04:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,968 ms / 6,000 ms |
コード長 | 2,241 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 86,412 KB |
最終ジャッジ日時 | 2024-12-03 00:04:46 |
合計ジャッジ時間 | 15,071 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
## https://yukicoder.me/problems/no/2412from collections import dequedef bfs(H, W, cum_s_array):passed = [[False] * (W - 2) for _ in range(H - 2)]passed[0][0] = Truequeue = deque()queue.append((0, 0))while len(queue) > 0:h, w = queue.popleft()for dh in range(-1, 2):for dw in range(-1, 2):if dh == 0 and dw == 0:continuenew_h = dh + hnew_w = dw + wif 0 <= new_h < H - 2 and 0 <= new_w < W - 2:if cum_s_array[new_h + 3][new_w + 3] - cum_s_array[new_h][new_w + 3] - cum_s_array[new_h + 3][new_w] + cum_s_array[new_h][new_w]== 0:if not passed[new_h][new_w]:passed[new_h][new_w] = Truequeue.append((new_h, new_w))return passed[-1][-1]def reachable(H, W, s_array):# 累積和計算cum_s_array = [[0] * (W + 1) for _ in range(H + 1)]for h in range(H):cum_row = 0for w in range(W):cum_row += s_array[h][w]cum_s_array[h + 1][w + 1] = cum_row + cum_s_array[h][w + 1]# BFSによる探索return bfs(H, W, cum_s_array)def main():H, W = map(int, input().split())S = []for _ in range(H):S.append(input())# 迷路のベースを作成s_array = []for s in S:row = []for i in range(len(s)):if s[i] == "#":row.append(1)else:row.append(0)s_array.append(row)if not reachable(H, W, s_array):print(0)returndef forbidden(h, w):if 0 <= h < 3 and 0 <= w < 3:return Trueif H - 3 <= h < H and W - 3 <= w < W:return Truereturn Falsefor h in range(H):for w in range(W):if S[h][w] == ".":if not forbidden(h, w):s_array[h][w] = 1if not reachable(H, W, s_array):print(1)returns_array[h][w] = 0print(2)if __name__ == '__main__':main()