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 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])