Submission #6202909

---

Source Code Expand

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

Judge Result