結果
問題 | No.86 TVザッピング(2) |
ユーザー |
|
提出日時 | 2024-03-05 21:37:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 5,000 ms |
コード長 | 2,481 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,140 KB |
実行使用メモリ | 58,264 KB |
最終ジャッジ日時 | 2024-09-29 18:04:51 |
合計ジャッジ時間 | 2,884 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sysimport mathimport bisectfrom heapq import heapify, heappop, heappushfrom collections import deque, defaultdict, Counterfrom functools import lru_cachefrom itertools import accumulate, combinations, permutations, productsys.setrecursionlimit(1000000)MOD = 10 ** 9 + 7MOD99 = 998244353input = lambda: sys.stdin.readline().strip()NI = lambda: int(input())NMI = lambda: map(int, input().split())NLI = lambda: list(NMI())SI = lambda: input()SMI = lambda: input().split()SLI = lambda: list(SMI())EI = lambda m: [NLI() for _ in range(m)]def main():H, W = NMI()A = [SI() for _ in range(H)]total = sum(a.count(".") for a in A)# DRULDH = [1, 0, -1, 0]DW = [0, 1, 0, -1]INF = 10**5for sh in range(H):for sw in range(W):if A[sh][sw] == "#":continuesteps = [[-INF]*W for _ in range(H)]h, w = sh, swR = 0d = 0steps[sh][sw] = 1while True:# print(h, w, d)rd = (d-1) % 4nrh, nrw = h+DH[rd], w+DW[rd]if 0 <= nrh < H and 0 <= nrw < W:if A[nrh][nrw] == ".":if R == 1:print("NO")returnelse:R += 1d = rdnh, nw = h+DH[d], w+DW[d]if 0 <= nh < H and 0 <= nw < W:if A[nh][nw] == "#":d = (d+1) % 4else:d = (d+1) % 4nh, nw = h+DH[d], w+DW[d]# print(nh, nw)if 0 <= nh < H and 0 <= nw < W:if nh == sh and nw == sw:# print(*steps, sep="\n")if steps[h][w] == total:print("YES")returnelse:print("NO")returnelif steps[nh][nw] >= 0:print("NO")returnelse:steps[nh][nw] = steps[h][w] + 1h = nhw = nwelse:print("NO")returnif __name__ == "__main__":main()