結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
75,568 KB
testcase_01 AC 81 ms
76,860 KB
testcase_02 AC 77 ms
76,444 KB
testcase_03 AC 173 ms
79,936 KB
testcase_04 AC 195 ms
80,624 KB
testcase_05 AC 441 ms
101,088 KB
testcase_06 AC 439 ms
99,036 KB
testcase_07 AC 434 ms
99,396 KB
testcase_08 AC 478 ms
101,856 KB
testcase_09 AC 447 ms
99,888 KB
testcase_10 AC 73 ms
75,304 KB
testcase_11 AC 72 ms
75,296 KB
testcase_12 AC 179 ms
80,428 KB
testcase_13 AC 182 ms
80,504 KB
testcase_14 AC 216 ms
81,060 KB
testcase_15 AC 182 ms
80,864 KB
testcase_16 AC 257 ms
84,104 KB
testcase_17 AC 217 ms
81,536 KB
testcase_18 AC 242 ms
82,648 KB
testcase_19 AC 234 ms
83,128 KB
testcase_20 AC 146 ms
79,136 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