結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー ckawatak
提出日時 2018-12-16 21:20:34
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,408 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 93,184 KB
最終ジャッジ日時 2024-09-25 06:36:49
合計ジャッジ時間 6,880 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from queue import Queue

N,V,Ox,Oy = list(map(int, input().split(' ')))

desert = []
for _ in range(N):
    desert.append(list(map(int, input().split(' '))))

visited = []
for _ in range(N):
    visited.append([0 for _ in range(N)])

def reset():
    for i in range(N):
        for j in range(N):
            visited[i][j] = 0

def bfs(sx,sy,sv,gx,gy):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    gvs = []
    
    reset()
    que = Queue()
    que.put((sx,sy,sv))

    while 0 < que.qsize():
        x,y,v = que.get()

        if x == gx and y == gy:
            gvs.append(v)

        visited[y][x] = 1
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx and nx < N and 0 <= ny and ny < N and visited[ny][nx] == 0:
                nv = v - desert[ny][nx]
                if nx == Ox-1 and ny == Oy-1:
                    nv = 2 * nv
                    
                if 0 < nv:
                    que.put((nx,ny,nv))
                
    return gvs

ov = 0
if Ox != 0 and Oy != 0:
    ovs = bfs(0,0,V,Ox-1,Oy-1)
    ovs = sorted(ovs,reverse=True)
    ov = ovs[0] if 0 < len(ovs) else 0

if ov == 0:
    sx = 0
    sy = 0
    sv = V
else:
    sx = Ox-1
    sy = Oy-1
    sv = ov
    
gvs = bfs(sx,sy,sv,N-1,N-1)
gvs = sorted(gvs,reverse=True)
gv = gvs[0] if 0 < len(gvs) else 0

if 0 < gv:
    print('YES')
else:
    print('NO')
0