結果

問題 No.1638 Robot Maze
ユーザー tcltktcltk
提出日時 2021-10-17 06:30:39
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
MLE  
実行時間 -
コード長 1,394 bytes
コンパイル時間 655 ms
コンパイル使用メモリ 11,888 KB
実行使用メモリ 655,304 KB
最終ジャッジ日時 2023-10-17 22:24:05
合計ジャッジ時間 4,859 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
10,780 KB
testcase_01 AC 33 ms
10,780 KB
testcase_02 AC 33 ms
10,780 KB
testcase_03 MLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#!/usr/bin/env python3
# from typing import *

import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq


def input():
    return sys.stdin.readline()[:-1]


# sys.setrecursionlimit(1000000)

# _INPUT = """3 3
# 1 1 1 1 8 16
# 1 1 3 1 
# ..@
# ##@
# ..@

# """
# sys.stdin = io.StringIO(_INPUT)

INF = 10**20

YES = 'Yes'
NO = 'No'

def solve():
    dist = [[[INF] * W for _ in range(H)] for _ in range(H*W+1)]

    hq = []
    dist[0][StartH][StartW] = 0
    heapq.heappush(hq, (0, 0, StartH, StartW))
    while hq:
        d, n, i, j = heapq.heappop(hq)
        for i1, j1, d1 in [(i-1, j, d+U), (i+1, j, d+D), (i, j-1, d+L), (i, j+1, d+R)]:
            n1 = n
            if not(0 <= i1 < H and 0 <= j1 < W) or C[i1][j1] == '#':
                continue
            elif C[i1][j1] == '@':
                n1 += 1
                if H*W < n1:
                    continue
            if d1 < dist[n1][i1][j1] and d1 + n1*P <= K:
                dist[n1][i1][j1] = d1
                heapq.heappush(hq, (d1, n1, i1, j1))
    return min(dist[n][GoalH][GoalW] + n*P for n in range(H*W+1))

H, W = map(int, input().split())
U, D, R, L, K, P = map(int, input().split())
StartH, StartW, GoalH, GoalW = map(lambda x: int(x)-1, input().split())
C = [input() for _ in range(H)]

cost = solve()
if cost <= K:
    print('Yes')
else:
    print('No')
0