Submission #6202909


Source Code Expand

Copy
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
C = ['#' * (M+2)]
C += ['#' + input().rstrip() + '#' for _ in range(N)]
C.append('#' * (M+2))

for i,row in enumerate(C):
  idx = row.find('g')
  if idx != -1:
    gx,gy = i, idx
    break

# (その場所からゴールに向かうときの明るさの最大値)
D = [[-1] * (M+2) for _ in range(N+2)]
D[gx][gy] = 10
q = []
# -1倍して入れる
heappush(q, (-10, gx, gy))

answer = -1
while q:
  if answer != -1:
    break
  d,x,y = heappop(q)
  if D[x][y] > -d:
    continue
  d *= -0.99
  for dx,dy in ([-1,0], [1,0], [0,-1], [0,1]):
    x1,y1 = x+dx, y+dy
    c = C[x1][y1]
    if c in 'g#':
      continue
    if c == 's':
      answer = d
      break
    d1 = float(c)
    if d1 > d:
      d1 = d
    if D[x1][y1] < d1:
      D[x1][y1] = d1
      heappush(q, (-d1, x1, y1))
        
    
print(answer)

Submission Info

Submission Time
Task C - 暗闇帰り道
User maspy
Language Python (3.4.3)
Score 100
Code Size 963 Byte
Status AC
Exec Time 1446 ms
Memory 13152 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 18 ms 3188 KB
00_mini_02.txt AC 18 ms 3188 KB
00_mini_03.txt AC 18 ms 3188 KB
00_mini_04.txt AC 18 ms 3188 KB
00_mini_05.txt AC 18 ms 3188 KB
00_sample_01.txt AC 18 ms 3188 KB
00_sample_02.txt AC 18 ms 3188 KB
01_rnd_01.txt AC 748 ms 7796 KB
01_rnd_02.txt AC 203 ms 5108 KB
01_rnd_03.txt AC 31 ms 3444 KB
01_rnd_04.txt AC 85 ms 3828 KB
01_rnd_05.txt AC 37 ms 3316 KB
01_rnd_06.txt AC 27 ms 3188 KB
01_rnd_07.txt AC 27 ms 3444 KB
01_rnd_08.txt AC 181 ms 4852 KB
01_rnd_09.txt AC 525 ms 6640 KB
01_rnd_10.txt AC 505 ms 6256 KB
01_rnd_11.txt AC 323 ms 5236 KB
01_rnd_12.txt AC 126 ms 4084 KB
01_rnd_13.txt AC 49 ms 3316 KB
01_rnd_14.txt AC 447 ms 5860 KB
01_rnd_15.txt AC 128 ms 4340 KB
01_rnd_16.txt AC 20 ms 3572 KB
01_rnd_17.txt AC 19 ms 3956 KB
01_rnd_18.txt AC 24 ms 3188 KB
01_rnd_19.txt AC 19 ms 3444 KB
01_rnd_20.txt AC 20 ms 3188 KB
02_maxrnd_01.txt AC 638 ms 8176 KB
02_maxrnd_02.txt AC 202 ms 6508 KB
02_maxrnd_03.txt AC 448 ms 7156 KB
02_maxrnd_04.txt AC 334 ms 6644 KB
02_maxrnd_05.txt AC 474 ms 7156 KB
02_maxrnd_06.txt AC 1067 ms 9076 KB
02_maxrnd_07.txt AC 78 ms 5748 KB
02_maxrnd_08.txt AC 68 ms 5744 KB
02_maxrnd_09.txt AC 825 ms 8180 KB
02_maxrnd_10.txt AC 113 ms 5748 KB
02_maxrnd_11.txt AC 564 ms 7264 KB
02_maxrnd_12.txt AC 373 ms 6644 KB
02_maxrnd_13.txt AC 369 ms 6644 KB
02_maxrnd_14.txt AC 464 ms 6900 KB
02_maxrnd_15.txt AC 181 ms 6004 KB
02_maxrnd_16.txt AC 510 ms 7156 KB
02_maxrnd_17.txt AC 471 ms 7016 KB
02_maxrnd_18.txt AC 38 ms 5492 KB
02_maxrnd_19.txt AC 25 ms 5364 KB
03_hard_01.txt AC 1405 ms 11380 KB
03_hard_02.txt AC 1371 ms 11380 KB
03_hard_03.txt AC 485 ms 8308 KB
03_hard_04.txt AC 541 ms 8436 KB
03_hard_05.txt AC 1396 ms 11380 KB
03_hard_06.txt AC 1446 ms 11380 KB
03_hard_07.txt AC 508 ms 8308 KB
03_hard_08.txt AC 518 ms 8436 KB
04_open_01.txt AC 1440 ms 11380 KB
04_open_02.txt AC 1431 ms 13152 KB
05_minihard_01.txt AC 23 ms 3188 KB
05_minihard_02.txt AC 23 ms 3188 KB
05_minihard_03.txt AC 20 ms 3188 KB
05_minihard_04.txt AC 20 ms 3188 KB
05_minihard_05.txt AC 23 ms 3188 KB
05_minihard_06.txt AC 23 ms 3188 KB
05_minihard_07.txt AC 20 ms 3188 KB
05_minihard_08.txt AC 20 ms 3188 KB