Submission #116800


Source Code Expand

Copy
from collections import namedtuple
from heapq import heappush, heappop

class P(namedtuple("P", ("brightness", "place"))):
    __lt__ = lambda self, other: not super().__lt__(other)

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]

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

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


SP = divmod(''.join(C).find("g"), M + 2)

memo = [[0 for _ in l] for l in C]

def get_C(place):
    n, m = place
    return C[n][m]

def get_memo(place):
    n, m = place
    return memo[n][m]

def set_memo(place, value):
    global memo
    n, m = place
    memo[n][m] = value

h = [P(10.0, SP)]

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

    for d in D:
        p_ = tuple(map(sum, zip(p, d)))
        l = get_C(p_)
        
        if l == 's':
            print(b * 0.99)
            exit(0)
        
        if l in ('#', 'g'):
            continue

        b_ = min(float(l), b * 0.99)
        
        if b_ > get_memo(p_):
            set_memo(p_, b_)
            heappush(h, P(b_, p_))

print(-1)

Submission Info

Submission Time
Task C - 暗闇帰り道
User misolmiso
Language Python (3.2.3)
Score 0
Code Size 1141 Byte
Status TLE
Exec Time 5040 ms
Memory 16060 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 57
TLE × 7
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 456 ms 8752 KB
00_mini_02.txt AC 154 ms 8736 KB
00_mini_03.txt AC 189 ms 8720 KB
00_mini_04.txt AC 148 ms 8736 KB
00_mini_05.txt AC 149 ms 8744 KB
00_sample_01.txt AC 150 ms 8780 KB
00_sample_02.txt AC 148 ms 8740 KB
01_rnd_01.txt AC 4261 ms 14616 KB
01_rnd_02.txt AC 1280 ms 11576 KB
01_rnd_03.txt AC 226 ms 9228 KB
01_rnd_04.txt AC 555 ms 9772 KB
01_rnd_05.txt AC 268 ms 9116 KB
01_rnd_06.txt AC 194 ms 8860 KB
01_rnd_07.txt AC 203 ms 9112 KB
01_rnd_08.txt AC 1152 ms 11200 KB
01_rnd_09.txt AC 3086 ms 13620 KB
01_rnd_10.txt AC 2915 ms 13036 KB
01_rnd_11.txt AC 1983 ms 11536 KB
01_rnd_12.txt AC 774 ms 10240 KB
01_rnd_13.txt AC 324 ms 9116 KB
01_rnd_14.txt AC 2689 ms 12644 KB
01_rnd_15.txt AC 796 ms 10404 KB
01_rnd_16.txt AC 158 ms 9420 KB
01_rnd_17.txt AC 159 ms 9908 KB
01_rnd_18.txt AC 177 ms 8972 KB
01_rnd_19.txt AC 153 ms 9324 KB
01_rnd_20.txt AC 167 ms 8860 KB
02_maxrnd_01.txt AC 3964 ms 15808 KB
02_maxrnd_02.txt AC 1282 ms 13392 KB
02_maxrnd_03.txt AC 2535 ms 13952 KB
02_maxrnd_04.txt AC 1952 ms 13416 KB
02_maxrnd_05.txt AC 2860 ms 14396 KB
02_maxrnd_06.txt TLE 5039 ms 16060 KB
02_maxrnd_07.txt AC 509 ms 12464 KB
02_maxrnd_08.txt AC 439 ms 12224 KB
02_maxrnd_09.txt AC 4829 ms 15820 KB
02_maxrnd_10.txt AC 702 ms 12256 KB
02_maxrnd_11.txt AC 3269 ms 14400 KB
02_maxrnd_12.txt AC 2233 ms 13488 KB
02_maxrnd_13.txt AC 2202 ms 13552 KB
02_maxrnd_14.txt AC 2719 ms 14016 KB
02_maxrnd_15.txt AC 1070 ms 12736 KB
02_maxrnd_16.txt AC 3050 ms 14272 KB
02_maxrnd_17.txt AC 2747 ms 14072 KB
02_maxrnd_18.txt AC 264 ms 11892 KB
02_maxrnd_19.txt AC 186 ms 11840 KB
03_hard_01.txt TLE 5039 ms 15712 KB
03_hard_02.txt TLE 5037 ms 15764 KB
03_hard_03.txt AC 2408 ms 14812 KB
03_hard_04.txt AC 2357 ms 14768 KB
03_hard_05.txt TLE 5038 ms 15740 KB
03_hard_06.txt TLE 5040 ms 15680 KB
03_hard_07.txt AC 2360 ms 14780 KB
03_hard_08.txt AC 2344 ms 14784 KB
04_open_01.txt TLE 5036 ms 15728 KB
04_open_02.txt TLE 5036 ms 15808 KB
05_minihard_01.txt AC 178 ms 8724 KB
05_minihard_02.txt AC 178 ms 8736 KB
05_minihard_03.txt AC 156 ms 8864 KB
05_minihard_04.txt AC 156 ms 8864 KB
05_minihard_05.txt AC 174 ms 8852 KB
05_minihard_06.txt AC 170 ms 8740 KB
05_minihard_07.txt AC 152 ms 8736 KB
05_minihard_08.txt AC 151 ms 8740 KB