結果
| 問題 | No.971 いたずらっ子 |
| ユーザー |
 convexineq
|
| 提出日時 | 2020-01-17 21:50:29 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,291 bytes |
| コンパイル時間 | 214 ms |
| コンパイル使用メモリ | 12,800 KB |
| 実行使用メモリ | 213,972 KB |
| 最終ジャッジ日時 | 2024-06-25 19:32:11 |
| 合計ジャッジ時間 | 7,017 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
ソースコード
def dijkstra_grid(g,sx,sy):
from heapq import heappush,heappop
h,w = len(g),len(g[0])
dx4=[0, 1, 0,-1]
dy4=[1, 0,-1, 0]
INF = 10**9
dist = [[INF]*w for _ in range(h)] #startからの最短距離
dist[sx][sy] = 0
q = [(0,sx,sy)] #(そこまでの距離、点)
while q:
dv,vx,vy = heappop(q)
if vx==h-1 and vy==w-1: print(dv); exit()
if dist[vx][vy] < dv: continue
for i in range(4):
nx = vx + dx4[i]
ny = vy + dy4[i]
if nx < 0 or nx>=h or ny <0 or ny>=w: continue #範囲外？
#if b[nx][ny] == "#": continue #壁？
cost = b[nx][ny]
if dv + cost < dist[nx][ny]:
dist[nx][ny] = dv + cost
heappush(q, (dv + cost, nx,ny))
return dist
#######################################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read
#n,m,*d= [int(i) for i in read().split()]
#a,t,k = [int(i) for i in readline().split()]
h,w = [int(i) for i in readline().split()]
bbb = read().split()
b = [[i+j+1 if bij=="k" else 1 for j,bij in enumerate(bi)] for i,bi in enumerate(bbb)]
dist = dijkstra_grid(b,0,0)
print(dist[-1][-1])