Submission #116805


Source Code Expand

Copy
from collections import namedtuple
from heapq import heappush, heappop

class P(tuple):
    __lt__ = lambda self, other: not super().__lt__(other)

N, M = map(int, input().strip().split())

D = [-1, 1, -(M + 2), M + 2]

C = ''.join(
    ['#' * (M + 2)] +
    ['#' + input().strip() + '#' for _ in range(N)] +
    ['#' * (M + 2)])

SP = C.find('g')

memo = [0 for _ in C]

h = [P((10.0, SP))]

while len(h) > 0:
    b, p = heappop(h)

    for d in D:
        p_ = p + d
        l = C[p_]
        
        if l == 's':
            print(b * 0.99)
            exit(0)
        
        if l == '#' or l == 'g':
            continue

        b_ = min(float(l), b * 0.99)
        
        if b_ > memo[p_]:
            memo[p_] = b_
            heappush(h, P((b_, p_)))

print(-1)

Submission Info

Submission Time
Task C - 暗闇帰り道
User misolmiso
Language Python (3.2.3)
Score 100
Code Size 819 Byte
Status AC
Exec Time 4524 ms
Memory 17692 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 398 ms 8748 KB
00_mini_02.txt AC 143 ms 8736 KB
00_mini_03.txt AC 146 ms 8744 KB
00_mini_04.txt AC 143 ms 8724 KB
00_mini_05.txt AC 146 ms 8736 KB
00_sample_01.txt AC 143 ms 8740 KB
00_sample_02.txt AC 143 ms 8648 KB
01_rnd_01.txt AC 2389 ms 14224 KB
01_rnd_02.txt AC 828 ms 11012 KB
01_rnd_03.txt AC 189 ms 9116 KB
01_rnd_04.txt AC 379 ms 9560 KB
01_rnd_05.txt AC 215 ms 8988 KB
01_rnd_06.txt AC 174 ms 8860 KB
01_rnd_07.txt AC 178 ms 9116 KB
01_rnd_08.txt AC 707 ms 10892 KB
01_rnd_09.txt AC 1804 ms 13068 KB
01_rnd_10.txt AC 1674 ms 12724 KB
01_rnd_11.txt AC 1146 ms 11316 KB
01_rnd_12.txt AC 481 ms 10012 KB
01_rnd_13.txt AC 241 ms 8980 KB
01_rnd_14.txt AC 1456 ms 12496 KB
01_rnd_15.txt AC 485 ms 10300 KB
01_rnd_16.txt AC 154 ms 9628 KB
01_rnd_17.txt AC 154 ms 10012 KB
01_rnd_18.txt AC 162 ms 8860 KB
01_rnd_19.txt AC 150 ms 9504 KB
01_rnd_20.txt AC 146 ms 8988 KB
02_maxrnd_01.txt AC 2340 ms 14864 KB
02_maxrnd_02.txt AC 837 ms 12856 KB
02_maxrnd_03.txt AC 1489 ms 13464 KB
02_maxrnd_04.txt AC 1159 ms 13212 KB
02_maxrnd_05.txt AC 1651 ms 14092 KB
02_maxrnd_06.txt AC 3360 ms 16284 KB
02_maxrnd_07.txt AC 373 ms 12700 KB
02_maxrnd_08.txt AC 320 ms 12700 KB
02_maxrnd_09.txt AC 2706 ms 15388 KB
02_maxrnd_10.txt AC 464 ms 12696 KB
02_maxrnd_11.txt AC 1839 ms 14104 KB
02_maxrnd_12.txt AC 1273 ms 13340 KB
02_maxrnd_13.txt AC 1249 ms 13332 KB
02_maxrnd_14.txt AC 1533 ms 13848 KB
02_maxrnd_15.txt AC 653 ms 12684 KB
02_maxrnd_16.txt AC 1673 ms 13976 KB
02_maxrnd_17.txt AC 1458 ms 13884 KB
02_maxrnd_18.txt AC 215 ms 12684 KB
02_maxrnd_19.txt AC 174 ms 12688 KB
03_hard_01.txt AC 4424 ms 17560 KB
03_hard_02.txt AC 4405 ms 17692 KB
03_hard_03.txt AC 903 ms 14600 KB
03_hard_04.txt AC 873 ms 14520 KB
03_hard_05.txt AC 4521 ms 17548 KB
03_hard_06.txt AC 4474 ms 17596 KB
03_hard_07.txt AC 893 ms 14604 KB
03_hard_08.txt AC 914 ms 14620 KB
04_open_01.txt AC 4350 ms 17596 KB
04_open_02.txt AC 4524 ms 17672 KB
05_minihard_01.txt AC 164 ms 8644 KB
05_minihard_02.txt AC 161 ms 8676 KB
05_minihard_03.txt AC 147 ms 8632 KB
05_minihard_04.txt AC 146 ms 8736 KB
05_minihard_05.txt AC 158 ms 8736 KB
05_minihard_06.txt AC 157 ms 8736 KB
05_minihard_07.txt AC 147 ms 8736 KB
05_minihard_08.txt AC 146 ms 8668 KB