結果

問題 No.86 TVザッピング(2)
ユーザー gew1fw
提出日時 2025-06-12 14:59:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,243 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 112,868 KB
最終ジャッジ日時 2025-06-20 14:02:45
合計ジャッジ時間 7,960 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 6 WA * 1 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

def main():
    N, M = map(int, stdin.readline().split())
    grid = [stdin.readline().strip() for _ in range(N)]
    
    dirs = [ ( -1, 0 ), (0, 1), (1, 0), (0, -1) ]  # up, right, down, left
    dir_names = ['U', 'R', 'D', 'L']
    dir_idx = { 'U':0, 'R':1, 'D':2, 'L':3 }
    
    total = 0
    for i in range(N):
        for j in range(M):
            if grid[i][j] == '.':
                total += 1
    if total == 1:
        print("NO")
        return
    
    def valid(x, y):
        return 0<=x<N and 0<=y<M and grid[x][y] == '.'
    
    visited = [[False for _ in range(M)] for __ in range(N)]
    path = []
    found = False
    
    def dfs(x, y, prev_dir, count, start_x, start_y):
        nonlocal found
        if found:
            return
        if count == total:
            if valid(start_x, start_y):
                nx = x + dirs[prev_dir][0]
                ny = y + dirs[prev_dir][1]
                if (nx == start_x and ny == start_y) or (nx == x and ny == y):
                    found = True
                    return
            else:
                nx = x + dirs[prev_dir][0]
                ny = y + dirs[prev_dir][1]
                if (nx, ny) == (start_x, start_y):
                    found = True
                    return
            return
        
        for d in [prev_dir, (prev_dir + 1) %4]:
            dx, dy = dirs[d]
            nx = x + dx
            ny = y + dy
            if valid(nx, ny) and not visited[nx][ny]:
                visited[nx][ny] = True
                path.append( (nx, ny, d) )
                dfs(nx, ny, d, count +1, start_x, start_y)
                if found:
                    return
                visited[nx][ny] = False
                path.pop()
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == '.':
                for d in range(4):
                    visited[i][j] = True
                    path = [ (i,j,d) ]
                    dfs(i, j, d, 1, i, j)
                    visited[i][j] = False
                    if found:
                        print("YES")
                        return
    
    print("NO")

if __name__ == "__main__":
    main()
0