結果

問題 No.86 TVザッピング(2)
コンテスト
ユーザー maspy
提出日時 2020-04-01 00:38:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 1,452 bytes
コンパイル時間 96 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-06-20 14:00:16
合計ジャッジ時間 1,868 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())
A = ['#' * (W + 2)]
for _ in range(H):
    A.append('#' + readline().decode().rstrip() + '#')
A += ['#' * (W + 2)]
A = tuple(''.join(A))

H += 2
W += 2
dx = (1, -W, -1, W)
S = A.index('.')
if A[S + 1] == '#' or A[S + W] == '#':
    print('NO')
    exit()


def get_path(i, di):
    x = S
    path = [x]
    se = set([x])
    while True:
        d = dx[i]
        if A[x + d] == '.':
            x += d
            if x in se:
                return path
            path.append(x)
            se.add(x)
            continue
        i = (i + di) % 4
        d = dx[i]
        if A[x + d] == '.':
            x += d
            if x in se:
                return path
            path.append(x)
            se.add(x)
            continue
        return path


path1 = get_path(0, -1)
path2 = []
P = get_path(3, 1)[1:]
n = sum(x == '.' for x in A)

seP = set(path1)
seQ = set()
p = 0

found = False
while path1:
    while True:
        if p < len(P) and ((P[p] not in seP) or (P[p] == path1[-1])):
            seQ.add(P[p])
            path2.append(P[p])
            p += 1
        else:
            break
    if path2 and path1[-1] == path2[-1] and len(path1) + len(path2) == n + 1:
        found = True
        break
    seP.remove(path1.pop())

print('YES' if found else 'NO')
0