Submission #116799


Source Code Expand

Copy
from collections import namedtuple
from collections import deque

P = namedtuple("P", ("time", "place"))
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("s"), 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

def clear_memo():
    global memo
    memo = [[0 for _ in l] for l in C]
    
def bfs(th, sp):
    q = deque()
    q.append(P(0, sp))

    clear_memo()

    while len(q) > 0:
        t, p = q.popleft()
        t_ = t + 1

        for d in D:
            p_ = tuple(map(sum, zip(p, d)))
            l = get_C(p_)
            
            if l == 'g':
                return True
            
            if l in ('#', 's'):
                continue

            b = int(l) * 0.99 ** t_
            
            if b > th and b > get_memo(p_):
                set_memo(p_, b)
                q.append(P(t_, p_))

    return False

lb = 0.
ub = 10.

for _ in range(30):
    th = lb + (ub - lb) / 2.

    if bfs(th, SP):
        lb = th
    else:
        ub = th

if lb == 0. and not bfs(0., SP):
    print(-1)
else:
    print(lb + (ub - lb) /2.)

Submission Info

Submission Time
Task C - 暗闇帰り道
User misolmiso
Language Python (3.2.3)
Score 0
Code Size 1502 Byte
Status WA
Exec Time 5041 ms
Memory 16388 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 18
WA × 13
TLE × 33
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 446 ms 8756 KB
00_mini_02.txt AC 149 ms 8876 KB
00_mini_03.txt AC 151 ms 8744 KB
00_mini_04.txt AC 143 ms 8856 KB
00_mini_05.txt AC 150 ms 8784 KB
00_sample_01.txt AC 162 ms 8860 KB
00_sample_02.txt AC 147 ms 8864 KB
01_rnd_01.txt TLE 5035 ms 15612 KB
01_rnd_02.txt TLE 5035 ms 11460 KB
01_rnd_03.txt AC 1061 ms 9484 KB
01_rnd_04.txt TLE 5036 ms 9876 KB
01_rnd_05.txt WA 953 ms 8988 KB
01_rnd_06.txt AC 352 ms 8840 KB
01_rnd_07.txt AC 1036 ms 9496 KB
01_rnd_08.txt TLE 5035 ms 12204 KB
01_rnd_09.txt TLE 5035 ms 13904 KB
01_rnd_10.txt TLE 5039 ms 13696 KB
01_rnd_11.txt TLE 5036 ms 11824 KB
01_rnd_12.txt TLE 5036 ms 10976 KB
01_rnd_13.txt WA 2497 ms 9240 KB
01_rnd_14.txt TLE 5035 ms 13452 KB
01_rnd_15.txt TLE 5040 ms 11808 KB
01_rnd_16.txt AC 356 ms 10052 KB
01_rnd_17.txt TLE 5037 ms 11716 KB
01_rnd_18.txt AC 204 ms 9116 KB
01_rnd_19.txt AC 254 ms 9836 KB
01_rnd_20.txt AC 214 ms 9116 KB
02_maxrnd_01.txt TLE 5041 ms 15384 KB
02_maxrnd_02.txt TLE 5036 ms 14864 KB
02_maxrnd_03.txt TLE 5037 ms 15516 KB
02_maxrnd_04.txt TLE 5040 ms 16184 KB
02_maxrnd_05.txt TLE 5037 ms 15408 KB
02_maxrnd_06.txt TLE 5035 ms 16148 KB
02_maxrnd_07.txt TLE 5039 ms 14644 KB
02_maxrnd_08.txt AC 3354 ms 14104 KB
02_maxrnd_09.txt TLE 5038 ms 16388 KB
02_maxrnd_10.txt TLE 5038 ms 14868 KB
02_maxrnd_11.txt TLE 5035 ms 16280 KB
02_maxrnd_12.txt TLE 5035 ms 15872 KB
02_maxrnd_13.txt TLE 5038 ms 16276 KB
02_maxrnd_14.txt TLE 5037 ms 16008 KB
02_maxrnd_15.txt TLE 5039 ms 14560 KB
02_maxrnd_16.txt TLE 5037 ms 15588 KB
02_maxrnd_17.txt TLE 5036 ms 14956 KB
02_maxrnd_18.txt AC 2150 ms 14064 KB
02_maxrnd_19.txt AC 1434 ms 14044 KB
03_hard_01.txt TLE 5036 ms 15984 KB
03_hard_02.txt TLE 5041 ms 15636 KB
03_hard_03.txt WA 2491 ms 14060 KB
03_hard_04.txt WA 3234 ms 14084 KB
03_hard_05.txt TLE 5036 ms 15884 KB
03_hard_06.txt TLE 5037 ms 16108 KB
03_hard_07.txt WA 2421 ms 14092 KB
03_hard_08.txt WA 3204 ms 14152 KB
04_open_01.txt TLE 5037 ms 16172 KB
04_open_02.txt TLE 5037 ms 15768 KB
05_minihard_01.txt WA 454 ms 8864 KB
05_minihard_02.txt WA 478 ms 8860 KB
05_minihard_03.txt WA 362 ms 8860 KB
05_minihard_04.txt WA 397 ms 8844 KB
05_minihard_05.txt WA 458 ms 8860 KB
05_minihard_06.txt WA 531 ms 8848 KB
05_minihard_07.txt AC 351 ms 8896 KB
05_minihard_08.txt WA 376 ms 8856 KB