結果

問題 No.2928 Gridpath
コンテスト
ユーザー detteiuu
提出日時 2024-10-12 16:02:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,277 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 241 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 94,208 KB
最終ジャッジ日時 2024-10-12 16:02:44
合計ジャッジ時間 3,738 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1

def judge():
    que = deque()
    que.append((gh, gw))
    dist = [[-1]*W for _ in range(H)]
    dist[gh][gw] = visited[gh][gw]
    while que:
        h, w = que.popleft()
        if [h, w] == [sh, sw]:
            return True
        for dh, dw in direction:
            nh, nw = h+dh, w+dw
            if not (0<=nh<H and 0<=nw<W):
                continue
            if visited[nh][nw] != -1 and visited[h][w]-1 > visited[nh][nw]:
                return False
            if visited[nh][nw] != -1 and dist[nh][nw] == -1:
                dist[nh][nw] = dist[h][w]-1
                que.append((nh, nw))

def dfs(h, w, cnt):
    visited[h][w] = cnt
    cnt += 1
    if [h, w] == [gh, gw]:
        if judge():
            global ans
            ans += 1
        visited[h][w] = -1
        return
    for dh, dw in direction:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and visited[nh][nw] == -1:
            dfs(nh, nw, cnt)
    cnt -= 1
    visited[h][w] = -1 
    return

visited = [[-1]*W for _ in range(H)]
ans = 0
direction = [(-1,0),(0,1),(1,0),(0,-1)]
dfs(sh, sw, 0)

print(ans)
0