結果

問題 No.20 砂漠のオアシス
ユーザー nebukuro09nebukuro09
提出日時 2016-09-21 13:30:34
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 510 ms / 5,000 ms
コード長 2,220 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 76,936 KB
実行使用メモリ 101,756 KB
最終ジャッジ日時 2024-04-21 06:56:02
合計ジャッジ時間 6,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
75,672 KB
testcase_01 AC 82 ms
76,948 KB
testcase_02 AC 86 ms
76,192 KB
testcase_03 AC 227 ms
79,944 KB
testcase_04 AC 202 ms
80,888 KB
testcase_05 AC 480 ms
100,956 KB
testcase_06 AC 458 ms
99,208 KB
testcase_07 AC 446 ms
99,520 KB
testcase_08 AC 510 ms
101,756 KB
testcase_09 AC 463 ms
99,880 KB
testcase_10 AC 78 ms
75,312 KB
testcase_11 AC 76 ms
75,420 KB
testcase_12 AC 179 ms
80,208 KB
testcase_13 AC 188 ms
80,120 KB
testcase_14 AC 223 ms
80,684 KB
testcase_15 AC 200 ms
80,736 KB
testcase_16 AC 268 ms
84,228 KB
testcase_17 AC 225 ms
81,536 KB
testcase_18 AC 249 ms
82,524 KB
testcase_19 AC 247 ms
82,996 KB
testcase_20 AC 153 ms
79,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def manhattan(node, goal):
    return 0

def astar(n, graph, start, goal):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    openlist = []
    in_open = set()
    in_closed = set()
    f = {(i, j):float('inf') for i in xrange(n) for j in xrange(n)}
 
    f[start] = manhattan(start, goal)
    heapq.heappush(openlist, (f[start], start))
    in_open.add(start)

    while len(openlist) != 0:
        fval, node = heapq.heappop(openlist)
        if node not in in_open:
            continue
        elif fval != f[node]:
            continue
        
        if node == goal:
            return f[node]

        in_open.remove(node)
        in_closed.add(node)

        for next_node in [(node[0]+dx[i], node[1]+dy[i]) for i in xrange(4)]:
            if next_node[0] < 0 or next_node[0] >= n or next_node[1] < 0 or next_node[1] >= n:
                continue
            gn = fval - manhattan(node, goal)
            fdm = gn + graph[next_node[0]][next_node[1]] + manhattan(next_node, goal)
            if next_node not in in_open and next_node not in in_closed:
                f[next_node] = fdm
                heapq.heappush(openlist, (fdm, next_node))
                in_open.add(next_node)
            elif next_node in in_open:
                if fdm < f[next_node]:
                    f[next_node] = fdm
                    heapq.heappush(openlist, (fdm, next_node))
            elif next_node in in_closed:
                if fdm < f[next_node]:
                    f[next_node] = fdm
                    heapq.heappush(openlist, (fdm, next_node))
                    in_open.add(next_node)
                    in_closed.remove(next_node)
    return -1

def parse():
    N, V, Ox, Oy = map(int, raw_input().split())
    graph = [map(int, raw_input().split()) for _ in xrange(N)]
    return N, V, graph, (Oy-1, Ox-1)

def run():
    n, v, graph, oasis = parse()
    c1 = astar(n, graph, (0, 0), (n-1, n-1))
    if oasis == (-1, -1):
        print 'YES' if c1 < v else 'NO'
        return
    c2 = astar(n, graph, (0, 0), oasis)
    c3 = astar(n, graph, oasis, (n-1, n-1))
    #print c1, c2, c3
    print 'YES' if c1 < v or (c2 < v and c3 < (v-c2)*2) else 'NO'

if __name__ == '__main__':
    run()
0