Problem:
Problem D: Cliff Climbing At 17:00, special agent Jack starts to escape from the enemy camp.
There is a cliff in between the camp and the nearest safety zone.
Jack has to climb the almost vertical cliff 
by stepping his feet on the blocks that cover the cliff.
The cliff has slippery blocks where Jack has to
spend time to take each step. 
He also has to bypass some blocks that are too loose to support his weight.
Your mission is to write a program that calculates the minimum time to complete climbing. Figure D-1 shows an example of cliff data that you will
receive.
The cliff is covered with square blocks.
Jack starts cliff climbing from the ground under the cliff,
by stepping his left or right foot on one of the blocks marked with
'S' at the bottom row.
The numbers on the blocks are the "slippery levels".  It takes t time units for him to safely put his foot on a
block marked with t , where 1 ≤ t ≤ 9.
He cannot put his feet on blocks marked with 'X'.
He completes the climbing when he puts 
either of his feet on one of the blocks marked with 'T' at the top row.   Figure D-1: Example of Cliff Data  Jack's movement must meet the following constraints. 
After putting his left (or right) foot on a block, he can only move
his right (or left, respectively) foot.
His left foot position ( lx , ly ) and his right foot position
( rx , ry ) should satisfy lx < rx and | lx - rx | + | ly - ry | ≤ 3 .
This implies that, given a position of his left foot in Figure D-2 (a), he has to
place his right foot on one of the nine blocks marked with blue color.
Similarly, given a position of his right foot in Figure D-2 (b),
he has to place his
left foot on one of the nine blocks marked with blue color.   Figure D-2: Possible Placements of Feet  Input The input is a sequence of datasets.
The end of the input is indicated by a line containing two zeros separated by a space.
Each dataset is formatted as follows:   w h  s(1,1) ... s(1,w)  s(2,1) ... s(2,w) ...  s(h,1) ... s(h,w)   The integers w and h are the width and the height of 
the matrix data of the cliff. You may assume 2 ≤ w ≤ 30 and 5 ≤ h ≤ 60.
Each of the following h lines consists of w characters
delimited by a space.
The character s(y, x) represents the state of the block at
position 
( x , y ) as follows:  'S': Jack can start cliff climbing from this block.  'T': Jack finishes climbing when he reaches this block.  'X': Jack cannot put his feet on this block.  '1' - '9' ( = t ): Jack has to spend t time units
to put either of his feet on this block.   You can assume that it takes no time to put a foot on a block marked with 'S' or 'T'. Output For each dataset, print a line only having a decimal integer indicating 
the minimum time required for the cliff climbing,
when Jack can complete it.
Otherwise, print a line only having "-1" for the dataset.
Each line should not have any characters other than these numbers. Sample Input 6 6
4 4 X X T T
4 7 8 2 X 7
3 X X X 1 8
1 2 X X X 6
1 1 2 4 4 7
S S 2 3 X X
2 10
T 1
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
2 10
T X
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
10 10
T T T T T T T T T T
X 2 X X X X X 3 4 X
9 8 9 X X X 2 9 X 9
7 7 X 7 3 X X 8 9 X
8 9 9 9 6 3 X 5 X 5
8 9 9 9 6 X X 5 X 5
8 6 5 4 6 8 X 5 X 5
8 9 3 9 6 8 X 5 X 5
8 3 9 9 6 X X X 5 X
S S S S S S S S S S
10 7
2 3 2 3 2 3 2 3 T T
1 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 4
3 2 3 2 3 2 3 2 3 5
3 2 3 1 3 2 3 2 3 5
2 2 3 2 4 2 3 2 3 5
S S 2 3 2 1 2 3 2 3
0 0 Output for the Sample Input 12
5
-1
22
12

Solution (Python):
from heapq import heappush, heappop

R_next = tuple((x, y) for x in range(-3, 0) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
L_next = tuple((x, y) for x in range(1, 4) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
c_num = tuple(str(i) for i in range(10))
L, R = 0, 1
INF = 10 ** 20

def conv(c):
  if c in c_num:
    return int(c)
  if c in ("T", "S"):
    return 0
  return -1

while True:
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [[-1] * 3 + input().split() + [-1] * 3 for _ in range(h)]
  for i in range(h):
    mp[i] = list(map(conv, mp[i]))
  mp.insert(0, [-1] * (w + 6))
  mp.insert(0, [-1] * (w + 6))
  mp.append([-1] * (w + 6))
  mp.append([-1] * (w + 6))
  start = []
  goal = []
  for x in range(3, w + 3):
    if mp[h + 1][x] == 0:
      start.append((x, h + 1))
    if mp[2][x] == 0:
      goal.append((x, 2))

  que = []
  dic = {}
  for x, y, in start:
    heappush(que, (0, x, y, L))
    heappush(que, (0, x, y, R))
    dic[(x, y, L)] = 0
    dic[(x, y, R)] = 0

  while que:
    total, x, y, foot = heappop(que)
    if foot == R:
      direct = R_next
      next_foot = L
    else:
      direct = L_next
      next_foot = R

    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      cost = mp[ny][nx]
      if cost == -1:
        continue
      if not (nx, ny, next_foot) in dic or dic[(nx, ny, next_foot)] > total + cost:
        dic[(nx, ny, next_foot)] = total + cost
        heappush(que, (total + cost, nx, ny, next_foot))
  
  ans = INF
  for x, y in goal:
    if (x, y, L) in dic: ans = min(ans, dic[(x, y, L)])
    if (x, y, R) in dic: ans = min(ans, dic[(x, y, R)])
  if ans == INF:
    print(-1)
  else:
    print(ans)

Solution (Python):
from heapq import heappush, heappop

R_next = tuple((x, y) for x in range(-3, 0) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
L_next = tuple((x, y) for x in range(1, 4) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
c_num = tuple(str(i) for i in range(10))
L, R = 0, 1
INF = 10 ** 20

def conv(c):
  if c in c_num:
    return int(c)
  if c in ("T", "S"):
    return 0
  return -1

while True:
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [[-1] * 3 + input().split() + [-1] * 3 for _ in range(h)]
  for i in range(h):
    mp[i] = list(map(conv, mp[i]))
  mp.insert(0, [-1] * (w + 6))
  mp.insert(0, [-1] * (w + 6))
  mp.append([-1] * (w + 6))
  mp.append([-1] * (w + 6))

  def search():
    start = []
    goal = []
    for x in range(3, w + 3):
      if mp[h + 1][x] == 0:
        start.append((x, h + 1))
      if mp[2][x] == 0:
        goal.append((x, 2))

    que = []
    dic = {}
    for x, y, in start:
      heappush(que, (0, x, y, L))
      heappush(que, (0, x, y, R))
      dic[(x, y, L)] = 0
      dic[(x, y, R)] = 0
 
    while que:
      total, x, y, foot = heappop(que)
      if foot == R:
        direct = R_next
        next_foot = L
      else:
        direct = L_next
        next_foot = R

      for dx, dy in direct:
        nx, ny = x + dx, y + dy
        if (nx, ny) in goal:
          return total
        cost = mp[ny][nx]
        if cost == -1:
          continue
        if not (nx, ny, next_foot) in dic or dic[(nx, ny, next_foot)] > total + cost:
          dic[(nx, ny, next_foot)] = total + cost
          heappush(que, (total + cost, nx, ny, next_foot))
    else:
      return -1
  print(search())

Solution (Python):
from heapq import heappush, heappop

R_next = tuple((x, y) for x in range(-3, 0) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
L_next = tuple((x, y) for x in range(1, 4) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
c_num = tuple(str(i) for i in range(10))
L, R = 0, 1
INF = 10 ** 20

def conv(c):
  if c in c_num:
    return int(c)
  if c in ("T", "S"):
    return 0
  return -1

while True:
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [[-1] * 3 + input().split() + [-1] * 3 for _ in range(h)]
  for i in range(h):
    mp[i] = list(map(conv, mp[i]))
  mp.insert(0, [-1] * (w + 6))
  mp.insert(0, [-1] * (w + 6))
  mp.append([-1] * (w + 6))
  mp.append([-1] * (w + 6))

  def search():
    start = []
    goal = []
    for x in range(3, w + 3):
      if mp[h + 1][x] == 0:
        start.append((x, h + 1))
      if mp[2][x] == 0:
        goal.append((x, 2))

    que = []
    visited = {}
    for x, y, in start:
      heappush(que, (0, x, y, L))
      heappush(que, (0, x, y, R))
      visited[(x, y, L)] = True
      visited[(x, y, R)] = True
 
    while que:
      total, x, y, foot = heappop(que)
      if foot == R:
        direct = R_next
        next_foot = L
      else:
        direct = L_next
        next_foot = R

      for dx, dy in direct:
        nx, ny = x + dx, y + dy
        if (nx, ny) in goal:
          return total
        cost = mp[ny][nx]
        if cost == -1:
          continue
        if not (nx, ny, next_foot) in visited:
          visited[(nx, ny, next_foot)] = True
          heappush(que, (total + cost, nx, ny, next_foot))
    else:
      return -1
  
  print(search())

Solution (Python):
from Queue import Queue
mvL=((-1, 0), (-1, 1), (-1, 2), (-1, -1), (-1, -2), (-2, 0), (-2, 1), (-2, -1), (-3, 0))
mvR=((1, 0), (1, 1), (1, 2), (1, -1), (1, -2), (2, 0), (2, 1), (2, -1), (3, 0))
mv=(mvL,mvR)
while True:
    w,h=map(int,raw_input().split())
    if w==h==0:break
    INF=1000
    LEFT,RIGHT=0,1
    S=[raw_input().split() for i in range(h)]
    D=[[[INF,INF] for j in range(w)] for i in range(h)]
    Q=Queue()
    posT=[]
    for i in range(h):
        for j in range(w):
            if S[i][j]=="S":
                Q.put((j,i,LEFT))
                Q.put((j,i,RIGHT))
                D[i][j][LEFT]=D[i][j][RIGHT]=0
            elif S[i][j]=="T":
                posT.append((j,i))
    while not Q.empty():
        x,y,foot=Q.get()
        if foot==RIGHT:
            for dx,dy in mv[LEFT]:
                mx=x+dx
                my=y+dy
                if 0<=mx<w and 0<=my<h and S[my][mx]!="X" and S[my][mx]!="S":
                    if S[my][mx]=="T":
                        cost=D[y][x][RIGHT]
                    else:
                        cost=int(S[my][mx])+D[y][x][RIGHT]
                    if D[my][mx][LEFT]>cost:
                        D[my][mx][LEFT]=cost
                        Q.put((mx,my,LEFT))
        elif foot==LEFT:
            for dx,dy in mv[RIGHT]:
                mx=x+dx
                my=y+dy
                if 0<=mx<w and 0<=my<h and S[my][mx]!="X" and S[my][mx]!="S":
                    if S[my][mx]=="T":
                        cost=D[y][x][LEFT]
                    else:
                        cost=int(S[my][mx])+D[y][x][LEFT]
                    if D[my][mx][RIGHT]>cost:
                        D[my][mx][RIGHT]=cost
                        Q.put((mx,my,RIGHT))
    minCost=INF
    for x,y in posT:
        minCost=min(minCost,D[y][x][LEFT])
        minCost=min(minCost,D[y][x][RIGHT])
    print minCost if minCost!=INF else -1

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def solve(H,W):
    grid = [input().split() for _ in range(H)]
    dist = [[[INF]*2 for _ in range(W)] for _ in range(H)]

    q = []
    
    g = []
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 'S':
                heappush(q,(0,i,j,0))
                heappush(q,(0,i,j,1))
                dist[i][j][0] = 0
                dist[i][j][1] = 0
            elif grid[i][j] == 'T':
                grid[i][j] = '0'
                g.append((i,j))

    
    t = ord('0')
    while q:
        d,ny,nx,leg = heappop(q)
        if d > dist[ny][nx][leg]:
            continue
        if leg == 0:
            for ly in range(max(ny - 2,0),min(ny + 3,H)):
                for lx in range(max(0,nx - 3),nx):
                    if abs(ly - ny) + abs(lx - nx) > 3:
                        continue
                    if grid[ly][lx] == 'X' or grid[ly][lx] == 'S':
                        continue
                    if dist[ly][lx][1] > dist[ny][nx][0] + ord(grid[ly][lx]) - t:
                        dist[ly][lx][1] = dist[ny][nx][0] + ord(grid[ly][lx]) - t
                        heappush(q,(dist[ly][lx][1],ly,lx,1))
        else:
            for ry in range(max(ny - 2,0),min(ny + 3,H)):
                for rx in range(nx + 1,min(nx + 4,W)):
                    if abs(ry - ny) + abs(rx - nx) > 3:
                        continue
                    if grid[ry][rx] == 'X' or grid[ry][rx] == 'S':
                        continue
                    if dist[ry][rx][0] > dist[ny][nx][1] + ord(grid[ry][rx]) - t:
                        dist[ry][rx][0] = dist[ny][nx][1] + ord(grid[ry][rx]) - t
                        heappush(q,(dist[ry][rx][0],ry,rx,0))

    ans = min(min(dist[gy][gx]) for gy,gx in g)
    print(-1 if ans == INF else ans)

def main():
    while True:
        W,H = map(int,input().split())
        if H == 0 and W == 0:
            return
        solve(H,W)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import bisect
import heapq
import copy
sys.setrecursionlimit(1000000)
from collections import deque
from itertools import permutations

def main():

    dy = [-2,-1,0,1,2,-1,0,1,0]
    rx = [1,1,1,1,1,2,2,2,3]
    lx = [-1,-1,-1,-1,-1,-2,-2,-2,-3]
    inf = 1000000007

    while True:
        m,n = map(int,input().split())
        if n == 0:break
        grid = []
        for _ in range(n):
            grid.append(list(input().split()))


        dp = [[[inf]*2 for _ in range(m)] for _ in range(n)]
        pq = []
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='S':
                    pq.append([0,i,j,0])
                    dp[i][j][0] = 0
                    pq.append([0,i,j,1])
                    dp[i][j][1] = 0
        heapq.heapify(pq)

        res = inf

        while pq:
            cost,i,j,b = heapq.heappop(pq)
            if dp[i][j][b]<cost:continue

            if grid[i][j] == 'T':
                res = cost
                break

            for k in range(9):
                h = i+dy[k]
                if b:w = j+lx[k]
                else:w = j+rx[k]
                bb = (b+1)%2
                if not (0<=h and h<n and 0<=w and w<m):continue
                if grid[h][w]=='X':continue
                if '1'<=grid[i][j]  and grid[i][j]<='9':
                    ncost = cost+int(grid[i][j])
                else :
                    ncost = copy.copy(cost)
                if ncost<dp[h][w][bb]:
                    dp[h][w][bb] = ncost
                    heapq.heappush(pq,[ncost,h,w,bb])

        print (res if res!=inf else -1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

def main():
    while True:
        w, h = map(int, input().split())
        if w == 0:
            break
        board = [input().strip().split() for i in range(h)]
        check = [[[False, False] for i in range(w)] for j in range(h)]
        q = []
        for y in range(h):
            for x in range(w):
                if board[y][x] == "S":
                    
                    check[y][x][0] = True
                    check[y][x][1] = True
                    heapq.heappush(q, (0, 0, x, y))
                    heapq.heappush(q, (0, 1, x, y))
        ok = False
        while len(q) > 0:
            cost, foot, x, y = heapq.heappop(q)
            if foot == 0:
                nexts = [(x+1, y-2), (x+1, y-1), (x+1, y), (x+1, y+1), (x+1, y+2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+3, y)]
            else:
                nexts = [(x-3, y), (x-2, y-1), (x-2, y), (x-2, y+1), (x-1, y-2), (x-1, y-1), (x-1, y), (x-1, y+1), (x-1, y+2)]
            
            next_foot = (foot + 1) % 2
            for nx, ny in nexts:
                if 0 <= nx and nx < w and 0 <= ny and ny < h:
                    if board[ny][nx] == "T":
                        print(cost)
                        ok = True
                        break
                    if (not check[ny][nx][next_foot]) and board[ny][nx] != "X":
                        check[ny][nx][next_foot] = True
                        heapq.heappush(q, (cost + int(board[ny][nx]), next_foot, nx, ny))

            if ok:
                break
        
        if not ok:
            print(-1)




if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def cal(x,y,f):
    return (x+y*W)*2+f

def dijkstra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0
    def search(s,w_0,q,weight):
        for t,w in lines[s]:
            w += w_0
            if weight[t] > w:
                heapq.heappush(q,[w,t])
                weight[t] = w
    q = [[0,s]]
    heapq.heapify(q)
    while q:
        w,n = heapq.heappop(q)
        search(n,w,q,weight)
    return weight


dxr = [ 1, 1, 1, 1, 1, 2, 2, 2, 3]
dyr = [-2,-1, 0, 1, 2,-1, 0, 1, 0]

dxl = [-1,-1,-1,-1,-1,-2,-2,-2,-3]
dyl = [-2,-1, 0, 1, 2,-1, 0, 1, 0]

while True:
    W,H = inpl()
    if W == 0:
        break
    ss = [list(input().split()) for _ in range(H)]

    N = W*H*2+2
    S = W*H*2
    T = W*H*2+1
    lines = defaultdict(set)
    for x in range(W):
        for y in range(H):
            if ss[y][x] == 'S':
                lines[S].add((cal(x,y,0),0))
                lines[S].add((cal(x,y,1),0))
            if ss[y][x] == 'T':
                lines[cal(x,y,0)].add((T,0))
                lines[cal(x,y,1)].add((T,0))
                continue
            if ss[y][x] == 'X':
                continue
            else:
                f = 0 
                for i in range(9):
                    tx = x + dxr[i]
                    ty = y + dyr[i]
                    if (0 <= tx < W) and (0 <= ty < H):
                        if ss[ty][tx] == 'S' or ss[ty][tx] == 'T':
                            cost = 0
                        elif ss[ty][tx] == 'X':
                            continue
                        else:
                            cost = int(ss[ty][tx])
                        lines[cal(x,y,0)].add((cal(tx,ty,1),cost))

                f = 1 
                for i in range(9):
                    tx = x + dxl[i]
                    ty = y + dyl[i]
                    if (0 <= tx < W) and (0 <= ty < H):
                        if ss[ty][tx] == 'S' or ss[ty][tx] == 'T':
                            cost = 0
                        elif ss[ty][tx] == 'X':
                            continue
                        else:
                            cost = int(ss[ty][tx])
                        lines[cal(x,y,1)].add((cal(tx,ty,0),cost))

    weights = dijkstra(lines,N,S)
    if weights[T] == INF:
        print(-1)
    else:
        print(weights[T])

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop,heappush
MA = 1000000
def v(y,x,d):
    if (x == 0 and d) or (x == w-1 and not d):
        return []
    k = 1-2*d
    l = [(i,x+k) for i in range(max(0,y-2),min(h,y+3))]
    if (x == 1 and d) or (x == w-2 and not d):
        return l
    for i in range(max(0,y-1),min(h,y+2)):
        l.append((i,x+2*k))
    if (x == 2 and d) or (x == w-3 and not d):
        return l
    l.append((y,x+3*k))
    return l

def dijkstra(start,goal):
    d = defaultdict(lambda : MA)
    q = []
    for y,x in start:
        for i in range(2):
            d[(y,x,i)] = 0
            heappush(q,(0,y,x,i))

    while q:
        dp,y,x,di = heappop(q)
        e = v(y,x,di)
        di ^= 1
        for y_,x_ in e:
            if s[y_][x_] == "X":continue
            cost = 0 if s[y_][x_] == "S" or s[y_][x_] == "T" else s[y_][x_]
            if dp+cost < d[(y_,x_,di)]: 
                d[(y_,x_,di)] = dp+cost
                heappush(q,(d[(y_,x_,di)],y_,x_,di))

    res = MA
    for y,x in goal:
        for i in range(2):
            if d[(y,x,i)] < res:
                res = d[(y,x,i)]
    res = res if res < MA else -1
    return res

def solve(w,h,s):
    start = []
    goal = []
    for y in range(h):
        for x in range(w):
            if s[y][x].isdecimal():
                s[y][x] = int(s[y][x])
            elif s[y][x] == "S":
                start.append((y,x))
            elif s[y][x] == "T":
                goal.append((y,x))
    print(dijkstra(start,goal))

while 1:
    w,h = map(int, sys.stdin.readline().split())
    if w == 0:
        break
    s = [sys.stdin.readline().split() for i in range(h)]
    solve(w,h,s)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []
    ddd = []
    for i in range(-2,3):
        for j in range(1,4):
            if abs(i)+j > 3:
                break
            ddd.append((i,j))

    while True:
        w,h = LI()
        if w == 0:
            break

        a = [LS() for _ in range(h)]
        b = [[int(c) if '1' <= c <= '9' else 0 for c in t] for t in a]

        def search():
            d = collections.defaultdict(lambda: inf)
            q = []
            for i in range(w):
                if a[-1][i] == 'S':
                    for j in [-1,1]:
                        s = (h-1, i, j)
                        d[s] = 0
                        heapq.heappush(q, (0, s))

            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True
                if a[u[0]][u[1]] == 'T':
                    return k

                for di, dj in ddd:
                    ni = u[0] + di
                    nj = u[1] + dj * u[2]
                    if ni < 0 or ni >= h or nj < 0 or nj >= w or a[ni][nj] == 'X':
                        continue
                    uv = (ni,nj,-u[2])

                    if v[uv]:
                        continue
                    ud = b[ni][nj]
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return -1

        rr.append(search())

    return '\n'.join(map(str, rr))



print(main())