Problem:


チーズ (Cheese)

問題

今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．JOI 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる．

この町には，N 個のチーズ工場があり，どの工場も１種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある．

ねずみの最初の体力は 1 であり，チーズを 1 個食べるごとに体力が 1 増える．ただし，ねずみは自分の体力よりも硬いチーズを食べることはできない．

ねずみは，東西南北に隣り合う区画に 1 分で移動することができるが，障害物の区画には入ることができない．チーズ工場をチーズを食べずに通り過ぎることもできる．すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け．ただし，ねずみがチーズを食べるのにかかる時間は無視できる． 

入力

入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≤ H ≤ 1000，1 ≤ W ≤ 1000，1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'，'X'，'.' からなる W 文字の文字列が書かれており，各々が各区画の状態を表している．北から i 番目，西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W)，第 i+1 行目の j 番目の文字は，区画 (i,j) が巣である場合は 'S' となり，障害物である場合は 'X' となり，空き地である場合は '.' となり，硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる．入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある．他のマスは障害物または空き地であることが保証されている．ねずみは全てのチーズを食べられることが保証されている．

出力

すべてのチーズを食べ終えるまでにかかる最短時間（分）を表す整数を 1 行で出力せよ．

入出力例

入力例 1
  

3 3 1
S..
...
..1

出力例 1

4

入力例 2
  

4 5 2
.X..1
....X
.XX.S
.2.X.

出力例 2

12

入力例 3
  

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

出力例 3

91

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 3 1
S..
...
..1


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque
import copy
h,w,n=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=deque([])
place=[[0,0] for _ in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=='S':
            queue.append([i,j,0])
            field[i][j]='.'
        elif field[i][j]!='X' and field[i][j]!='.':
            fact=int(field[i][j])
            field[i][j]='.'
            place[fact-1][0]=i
            place[fact-1][1]=j
#print(place)
#print(field)
ans=0
for i in range(n):
    if 1<=i:
        queue=deque([[place[i-1][0],place[i-1][1],0]])
#        print(queue)
    y=place[i][0]
    x=place[i][1]
    fi=copy.deepcopy(field)
    while True:
        hnow=queue[0][0]
        wnow=queue[0][1]
        time=queue[0][2]
        queue.popleft()
        time+=1
        if hnow+1<h:
            if hnow+1==y and wnow==x:
                break
            elif fi[hnow+1][wnow]=='.':
                fi[hnow+1][wnow]='v'
                queue.append([hnow+1,wnow,time])
        if wnow+1<w:
            if hnow==y and wnow+1==x:
                break
            elif fi[hnow][wnow+1]=='.':
                fi[hnow][wnow+1]='v'
                queue.append([hnow,wnow+1,time])
        
        if 0<=hnow-1:
            if hnow-1==y and wnow==x:
                break
            elif fi[hnow-1][wnow]=='.':
                fi[hnow-1][wnow]='v'
                queue.append([hnow-1,wnow,time])
        
        if 0<=wnow-1:
            if hnow==y and wnow-1==x:
                break
            elif fi[hnow][wnow-1]=='.':
                fi[hnow][wnow-1]='e'
                queue.append([hnow,wnow-1,time])
#        print(queue)
    ans+=time
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from queue import Queue

h,w,n = map(int,input().split())
map = [[0] * w for _ in range(h)]
for i in range(h):
    map[i] = list(input())

que = Queue()
ans = 0
checked = [[-1] * w for _ in range(h)]

def bfs():
    global que,ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == g[0] and xy[1] == g[1]:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                else:
                    if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                        if checked[xy[1]+j][xy[0]+i] == -1 and map[xy[1]+j][xy[0]+i] != "X":
                            checked[xy[1]+j][xy[0]+i] = checked[xy[1]][xy[0]] + 1
                            que.put([xy[0]+i,xy[1]+j])

mark = [[0,0] for _ in range(n+1)]
for i in range(h):
    for j in range(w):
        for k in range(1,n+1):
            if map[i][j] == str(k):
                mark[k] = [j,i]
            elif map[i][j] == "S":
                mark[0] = [j,i]

cnt = 0
for i in range(1,len(mark)):
    que = Queue()
    que.put([mark[i-1][0],mark[i-1][1]])
    g = [mark[i][0],mark[i][1]]
    ans = 0
    checked = [[-1] * w for _ in range(h)]
    checked[mark[i-1][1]][mark[i-1][0]] = 0
    bfs()
    cnt += ans

print(cnt)

Submission status: Accepted

Solution code:
import sys
import copy
from collections import defaultdict

nesw = [[0, 1], [0, -1], [1, 0], [-1, 0]]
height, width, factory = map(int, input().split(" "))
root = []
start_y, start_x = -1, -1
targets = defaultdict(int)
for h in range(height):
    temp = [n for n in input()]
    if start_y == -1:
        try:
            start_y, start_x = h, temp.index("S")
        except:
            pass
    for i in range(1, factory + 1):
        if not targets[i]:
            try:
                targets[i] = (h, temp.index(str(i)))
            except:
                pass
    root.append(temp)
targets[0] = (start_y, start_x)
fastest_root = {}

# print(targets)

for start in range(factory):
    h, w = targets[start]
    end = start + 1
    end_y, end_x = targets[end]
    used = [[0 for n in range(width)] for m in range(height)]
    queue = [(h, w)]
    used[h][w] = 1
    flag = 0
    turn = 0
    while True:
        new_queue = []
        for q in queue:
            h, w = q
            for t in nesw:
                new_h, new_w = h + t[0], w + t[1]
                if 0 <= new_h < height and 0 <= new_w < width:
                    if new_h == end_y and new_w == end_x:
                        fastest_root[start] = {end:turn + 1}
                        flag = 1
                        break
                    elif not used[new_h][new_w] and root[new_h][new_w] != "X":
                        used[new_h][new_w] = 1
                        new_queue.append((new_h, new_w))
        if flag:
            break
        queue = new_queue
        turn += 1

perm = [n for n in range(0, factory + 1)]
answer = 0
for i in range(factory):
    answer += fastest_root[perm[i]][perm[i + 1]]

print(answer)

Submission status: Accepted

Solution code:
import queue


class HW(object):
    def __init__(self, args: tuple):
        self.h = args[0]
        self.w = args[1]


h, w, n = map(int, input().split())
maze = [input() for i in range(h)]

start = HW((0, 0))
now = HW((0, 0))
nxt = HW((0, 0))

cnt = 0
visited = []


def bfs(target: int) -> int:
    global visited, start, h, w
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    q = queue.Queue()
    q.put((start.h, start.w))
    visited[start.h][start.w] = 0

    while not q.empty():
        tmp = q.get()
        now.h, now.w = tmp[0], tmp[1]
        if maze[now.h][now.w] == str(target):
            start = now
            return visited[now.h][now.w]

        for k in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nxt.h, nxt.w = now.h + k[0], now.w + k[1]
            if not 0 <= nxt.h < h or not 0 <= nxt.w < w:
                continue
            elif maze[nxt.h][nxt.w] == "X":
                continue
            elif visited[nxt.h][nxt.w] == -1:
                q.put((nxt.h, nxt.w))
                visited[nxt.h][nxt.w] = visited[now.h][now.w] + 1


def main() -> None:
    for j in range(h):
        for i in range(w):
            if maze[j][i] == "S":
                start.h, start.w = j, i

    for i in range(n):
        global cnt
        cnt += bfs(i + 1)
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  h, w, n = map(int, input().split())
  mp = ["X" + input() + "X" for _ in range(h)]
  mp.insert(0, "X" * (w + 2))
  mp.append("X" * (w + 2))
  
  poss = [None] * (n + 1)
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y][x] == "S":
        poss[0] = (x, y)
      elif "1" <= mp[y][x] <= "9":
        poss[int(mp[y][x])] = (x, y)
  
  ans = 0
  vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
  for i in range(n):
    sx, sy = poss[i]
    gx, gy = poss[i + 1]
    used = [[False] * (w + 2) for _ in range(h + 2)]
    used[sy][sx] = True
    que = deque()
    push = que.append
    pop = que.popleft
    push((0, sx, sy))
    while que:
      cnt, x, y = pop()
      if (x, y) == (gx, gy):
        ans += cnt
        break
      
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if used[ny][nx] or mp[ny][nx] == "X":continue
        used[ny][nx] = True
        push((cnt + 1, nx, ny))
  
  print(ans)

main()

Submission status: Accepted

Solution code:
def isnew(done, a, i):
    if done[a[0]][a[1]] == i:
        return False
    else:
        return True


h, w, n = map(int, input().split())

arr = []

s = [0, 0]

done = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == 'S':
            s = [i, j]
    arr.append(a)
    
step = 0
    
for i in range(1, n+1):
    pre = [s]
    now = []
    f = 0
    while f == 0:
        step += 1
        for j in range(len(pre)):
            if pre[j][0] != 0:
                p = arr[pre[j][0]-1][pre[j][1]]
                pp = [pre[j][0]-1, pre[j][1]]
                if p == str(i):
                    s = pp
                    f = 1
                    break
                elif p != 'X' and isnew(done, pp, i):
                    now.append(pp)
                    done[pre[j][0]-1][pre[j][1]] = i

            if pre[j][0] != h-1:
                p = arr[pre[j][0]+1][pre[j][1]]
                pp = [pre[j][0]+1, pre[j][1]]
                if p == str(i):
                    s = pp
                    f = 1
                    break
                elif p != 'X' and isnew(done, pp, i):
                    now.append(pp)
                    done[pre[j][0]+1][pre[j][1]] = i

            if pre[j][1] != 0:
                p = arr[pre[j][0]][pre[j][1]-1]
                pp = [pre[j][0], pre[j][1]-1]
                if p == str(i):
                    s = pp
                    f = 1
                    break
                elif p != 'X' and isnew(done, pp, i):
                    now.append(pp)
                    done[pre[j][0]][pre[j][1]-1] = i

            if pre[j][1] != w-1:
                p = arr[pre[j][0]][pre[j][1]+1]
                pp = [pre[j][0], pre[j][1]+1]
                if p == str(i):
                    s = pp
                    f = 1
                    break
                elif p!= 'X' and isnew(done, pp, i):
                    now.append(pp)
                    done[pre[j][0]][pre[j][1]+1] = i
            

        pre = []
        for k in range(len(now)):
            temp = []
            for l in range(2):
                temp.append(now[k][l])
            pre.append(temp)
        now = []
                
                

print(step)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        h, w, n = map(int, raw_input().split())
        board = [[None for j in range(w+1)] for i in range(h+1)]
        s = (None, None)
        nxt = 1
        ans = 0
        for i in range(1, h+1):
            row = raw_input()
            for j in range(1, w+1):
                board[i][j] = row[j-1]
                if board[i][j] == 'S':
                    s = (i, j, ans)
        # print board
        # print s
        # print board[3][3]
        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # print nxt
        q = [s]
        while nxt <= n:
            while q != []:
                y, x, ans = q.pop(0)
                # print y, x, ans, nxt
                # if (y, x) == (3, 3):
                #     print nxt
                #     print board[y][x]
                #     print nxt == board[y][x]
                if board[y][x] == str(nxt):
                    nxt += 1
                    q = [(y, x, ans)]
                    # print 'nxt: ' + str(nxt)
                    break
                ans += 1
                for dy, dx in d:
                    if 0 < y + dy <= h and 0 < x + dx <= w and board[y+dy][x+dx] != 'X':
                        q.append((y + dy, x + dx, ans))
        print ans
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        h, w, n = map(int, raw_input().split())
        board = [[None for j in range(w+1)] for i in range(h+1)]
        s = (None, None)
        ans = 0
        for i in range(1, h+1):
            row = raw_input()
            for j in range(1, w+1):
                board[i][j] = row[j-1]
                if board[i][j] == 'S':
                    s = (i, j, ans, [])
                elif board[i][j] == '1':
                    g = (i, j)
        # print board
        # print s
        # print board[3][3]
        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # print nxt
        q = [s]
        for nxt in range(1, n+1):
            # print q
            while q != []:
                y, x, ans, used = q.pop(0)
                # print y, x, ans, used
                # if (y, x) == (3, 3):
                #     print nxt
                #     print board[y][x]
                #     print nxt == board[y][x]
                # if board[y][x] == str(nxt):
                #     q = [(y, x, ans)]
                #     # print 'nxt: ' + str(nxt)
                #     break
                if y == g[0] and x == g[1]:
                    break
                ans += 1
                for dy, dx in d:
                    if 0 < y + dy <= h and 0 < x + dx <= w and board[y+dy][x+dx] != 'X' and (not (y + dy, x + dx) in used):
                        q.append((y + dy, x + dx, ans, used + [(y, x)]))
                        
            q = [(y, x, ans, [])]
            for i in range(1, h+1):
                for j in range(1, w+1):
                    if board[i][j] == str(nxt+1):
                        g = (i, j)
        # print q
        print ans
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Runtime Error

Solution code:
import queue

# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]


# initialization visited maps
def init_visited_maps(h, w):
    return [[True for i in range(w)] for j in range(h)]


# bfs algorithm
def bfs(h, w, cheese, maps, sx, sy, moves):
    que = queue.Queue()
    que.put((moves, sx, sy))

    visited = init_visited_maps(h, w)
    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x] and maps[n_y][n_x] != 'X'):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# simulate mouse
def simulate(h, w, n, maps, sx, sy):
    moves = 0
    x, y = sx, sy

    for i in range(1, n+1, 1):
        moves, x, y = bfs(h, w, str(i), maps, x, y, moves)

    return str(moves)


# main function
def main():
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    maps = []
    sx, sy = 0, 0
    for i in range(H):
        maps.append(input())
        for j in range(W):
            if maps[i][j] == 'S':
                sx, sy = j, i

    print(simulate(H, W, N, maps, sx, sy))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import queue


# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]


# bfs algorithm
def bfs(h, w, cheese, maps, sx, sy, moves, visited):
    que = queue.Queue()
    que.put((moves, sx, sy))

    for i in range(h):
        for j in range(w):
            visited[i][j] = True

    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x] and maps[n_y][n_x] != 'X'):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# simulate mouse
def simulate(h, w, n, maps, sx, sy):
    moves = 0
    x, y = sx, sy

    visited = [[True for i in range(w)] for j in range(h)]

    for i in range(1, n+1, 1):
        moves, x, y = bfs(h, w, str(i), maps, x, y, moves, visited)

    return str(moves)


# main function
def main():
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    maps = []
    sx, sy = 0, 0
    for i in range(H):
        maps.append(input())
        for j in range(W):
            if maps[i][j] == 'S':
                sx, sy = j, i

    print(simulate(H, W, N, maps, sx, sy))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import queue


# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]


visited = [[True for i in range(1000)] for j in range(1000)]
maps = []

# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = queue.Queue()
    que.put((moves, sx, sy))

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# simulate mouse
def simulate(h, w, n, sx, sy):
    moves = 0
    x, y = sx, sy

    #visited = [[True for i in range(w)] for j in range(h)]

    for i in range(1, n+1, 1):
        moves, x, y = bfs(h, w, str(i), x, y, moves)

    return str(moves)


# main function
def main():
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    del str

    #maps = []
    sx, sy = 0, 0
    for i in range(H):
        maps.append(input())
        for j in range(W):
            if maps[i][j] == 'S':
                sx, sy = j, i

    print(simulate(H, W, N, sx, sy))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import queue

# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]

# map info
visited = []
maps = []


# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = queue.Queue()
    que.put((moves, sx, sy))

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# main function
if __name__ == '__main__':
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    del str

    visited = [[True for i in range(W)] for j in range(H)]
    maps = ["" for i in range(H)]

    x, y = 0, 0
    for i in range(H):
        maps[i] = input()
        for j in range(W):
            if maps[i][j] == 'S':
                x, y = j, i

    moves = 0
    for i in range(1, N+1, 1):
        moves, x, y = bfs(H, W, str(i), x, y, moves)

    print(str(moves))

Submission status: Runtime Error

Solution code:
# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]

# map info
visited = []
maps = []

# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = [(moves, sx, sy)]

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while len(que) > 0:
        c_moves, c_x, c_y = que.pop(0)
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.append((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# main function
if __name__ == '__main__':
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    visited = [[True for i in range(W)] for j in range(H)]
    maps = ["" for i in range(H)]

    x, y = 0, 0
    for i in range(H):
        maps[i] = input()
        for j in range(W):
            if maps[i][j] == 'S':
                x, y = j, i

    moves = 0
    for i in range(1, N+1, 1):
        moves, x, y = bfs(H, W, str(i), x, y, moves)

    print(str(moves))

Submission status: Runtime Error

Solution code:
import  copy
h = w = 0
mymap =[]
const_mymap = []
qlist = []
ans = 0
def bfs(n):
    while True:
        if len(qlist) != 0:
            temp = qlist.pop(0)
            x = temp[0]
            y = temp[1]
            deep = temp[2]

            #print(temp)
            if mymap[y][x] == str(n):

                return temp
            mymap[y] = mymap[y][:x] + '*' + mymap[y][x + 1:]

            if x + 1 < w:
                if mymap[y][x + 1] not in '*X':
                    qlist.append([x + 1, y, deep + 1])
            if x - 1 >= 0:
                if mymap[y][x - 1] not in '*X':
                    qlist.append([x - 1, y, deep + 1])
            if y + 1 < h:
                if mymap[y + 1][x] not in '*X':
                    qlist.append([x, y + 1, deep + 1])
            if y - 1 >= 0:
                if mymap[y - 1][x] not in '*X':
                    qlist.append([x, y - 1, deep + 1])
        else:
            break
h, w, n = list(map(lambda x: int(x), input().split(" ")))
for i in range(0, h):
    const_mymap.append(input())

mymap = copy.deepcopy(const_mymap)

for i in range(0, h):
    for j in range(0, w):
        if mymap[i][j] == 'S':
            nstart = [j, i, 0]

qlist.append(nstart)

for i in range (n):
    mymap = copy.deepcopy(const_mymap)
    temp = bfs(i+1)
    #print(temp)
    #print(const_mymap)
    ans = temp[2]
    qlist = []
    qlist.append(temp)
    #print(ans)

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

vector = [[1,0],[-1,0],[0,1],[0,-1]]
matrix = []
visited = []
q = []

h,w,n = map(int,raw_input().split())
s_x = 0
s_y = 0

for i in xrange(h):
  matrix.append( list(raw_input()))
  visited.append([0]*w)
  if 'S' in matrix[i]:
    s_y = i
    s_x = matrix[i].index('S')

ans = 0
for t in xrange(n):
  t+=1
  q = []
#init visited
  visited = []
  for i in xrange(h):
    visited.append([0]*w)
#search start
  q.append((s_x,s_y,0))
  while 1:
    now = q.pop(0)
    visited[now[1]][now[0]] = 1
    if matrix[now[1]][now[0]] == str(t):
      s_x = now[0]
      s_y = now[1]
      ans += now[2]
      break
    for dv in vector:
      nx = now[0]+dv[0]
      ny = now[1]+dv[1]
      ns = now[2]+1
      if nx in xrange(w) and ny in xrange(h) and matrix[ny][nx]!='X' and visited[ny][nx] == 0:
        q.append((nx,ny,ns))
print ans

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)

def search(field,distance,ch,cv,eh,ev,step):
	if not (0<=ch<len(field)):		return
	if not (0<=cv<len(field[ch])):	return
	if field[ch][cv]=='X':			return
	if distance[ch][cv]<step: 		return

	distance[ch][cv] = step
	search(field,distance,ch+1,cv,eh,ev,step+1)
	search(field,distance,ch-1,cv,eh,ev,step+1)
	search(field,distance,ch,cv+1,eh,ev,step+1)
	search(field,distance,ch,cv-1,eh,ev,step+1)

def calculate_distance(field,locations,current_HP):
	ch,cv=locations[current_HP-1]
	eh,ev=locations[current_HP]
	distance=[[10**6 for _ in range(len(field[0]))] for __ in range(len(field))]
	search(field,distance,ch,cv,eh,ev,0)
#	print('='*50)
#	for v in distance:
#		print(v)
#	print('-'*50)
	return distance[eh][ev]
#	return 0

def solve(field,locations):
	total_step=0
	for current_HP in range(1,len(locations)):
		total_step += calculate_distance(field,locations,current_HP)
	return total_step

def main():
	line=input().strip()
	H,W,N=list(map(int,line.split(' ')))
	field,locations=list(),dict()
	for i in range(H):
		field.append(list(input().strip()))
		for j,x in enumerate(field[-1]):
			if x=='S':
				locations[0] = (i,j,)
			if x.isdigit():
				x = int(x)
				field[-1][j] = x
				locations[x] = (i,j,)
	print(solve(field,locations))

if __name__=='__main__':
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def get_shortest_distance(field,locations,current_HP):
	is_visit = [[False for _ in range(len(field[0]))] for __ in range(len(field))]
	frontier = set()
	frontier.add(locations[current_HP-1])
	for step in xrange(10**10):
		for cx,cy in frontier:
			if (cx,cy)==locations[current_HP]: return step
			is_visit[cx][cy]=True
		next_frontier = set()
		for cx,cy in list(frontier):
			for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
				nx = cx+dx
				ny = cy+dy
				if not (0<=nx<len(field)):		continue
				if not (0<=ny<len(field[nx])):	continue
				if field[nx][ny]=='X':			continue
				if is_visit[nx][ny]: 			continue
				next_frontier.add((nx,ny))
#		assert len(next_frontier)!=0,(current_HP,is_visit,frontier)
		frontier = next_frontier
#	assert True,('the goal is not reachable')

def solve(field,locations):
	total_step=0
	for current_HP in range(1,len(locations)):
		total_step += get_shortest_distance(field,locations,current_HP)
	return total_step

def main():
	line=input().strip()
	H,W,N=list(map(int,line.split(' ')))
	field,locations=list(),dict()
	for i in range(H):
		field.append(list(input().strip()))
		for j,x in enumerate(field[-1]):
			if x=='S':
				locations[0] = (i,j,)
			if x.isdigit():
				x = int(x)
				field[-1][j] = x
				locations[x] = (i,j,)
	print(solve(field,locations))

if __name__=='__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import numpy
sys.setrecursionlimit(1000000)

class MouseClass:
	def __init__(self):
		self.X = 0
		self.Y = 0
		self.LIFE = 1
		self.factoriesAble = []
		self.factoriesGone = []
		self.factoriesWill = []
		self.distance = 0

	def get_field(self, field:list):
		self.field = field

	def gen_factoriesInfo(self, factoriesInfo:list):
		self.factoriesAble = [i for i in factoriesInfo if i[2]<=self.LIFE]
		self.factoriesWill = [factory for factory in self.factoriesAble if factory not in self.factoriesGone]

	def findNearestFactory(self, factories:list):
		path = [abs(self.X-factory[0]) + abs(self.Y-factory[1]) for factory in factories]
		return factories[numpy.argmin(path)]

	def goFactory(self, factories:list):
		factory = self.findNearestFactory(factories)
		# print(abs(self.X-factory[0])+abs(self.Y-factory[1]))
		self.distance += self.calcShortestPath(self.X, self.Y, self.field, factory[0:2])
		self.X, self.Y = factory[0], factory[1]
		self.LIFE += 1
		self.factoriesGone.append(factory)

	def calcShortestPath(self, x:int, y:int, field:list, goal:list):
		print(x, y, goal)
		INF = 1000000
		d = []
		queue = []
		H = len(self.field)
		W = len(self.field[0])
		for _ in range(H):
			tmp = []
			for _ in range(W):
				tmp.append(INF)
			d.append(tmp)
				
		queue.append([x, y])
		d[x][y] = 0
		while len(queue)!=0:
			p = queue[0]
			queue.pop(0)
			if p==goal: break

			for dx in [-1, 0, 1]:
				if dx == -1: width = [0]
				if dx == 0: width = [-1, 1]
				if dx == 1: width = [0]
				for dy in width:
					nx = p[0]+dx
					ny = p[1]+dy
					if 0 <= nx < H and 0 <= ny < W:
						isObstacle = field[nx][ny] == "X"
						isNotVisited = d[nx][ny] == INF
						if (not isObstacle) and isNotVisited:
							queue.append([nx, ny])
							d[nx][ny] = d[p[0]][p[1]]+1
		return d[goal[0]][goal[1]] 

class FieldClass:
	def __init__(self):
		self.field = []
		self.Mouse = MouseClass()
		self.factoriesInfo = []

	def loadField(self):
		field = []
		i = 0
		H, W = 0, 0
		LINE_NUM = 0
		field = []
		while True:
			line = sys.stdin.readline().strip()
			LINE_NUM += 1
			if LINE_NUM == 1:
				line = line.split(" ")
				H, W = int(line[0]), int(line[1])
				continue
			self.field.append(list(line))
			if LINE_NUM == H+1: break

		self.Mouse.get_field(self.field)

	def initMousePos(self):
		H = len(self.field)
		W = len(self.field[0])
		for i in range(H):
			for j in range(W):
				if self.field[i][j] == "S":
					self.Mouse.X = i
					self.Mouse.Y = j

	def gen_factoriesInfo(self):
		NUM_LIST = [str(i) for i in range(10)]
		H = len(self.field)
		W = len(self.field[0])
		factories = []
		for i in range(H):
			for j in range(W):
				if self.field[i][j] in NUM_LIST:
					factories.append([i, j, int(self.field[i][j])])
		self.factoriesInfo = factories

Field = FieldClass()
Field.loadField()
Field.initMousePos()
Field.gen_factoriesInfo()

Field.Mouse.gen_factoriesInfo(Field.factoriesInfo)
while True:
	Field.Mouse.goFactory(Field.Mouse.factoriesWill)
	Field.Mouse.gen_factoriesInfo(Field.factoriesInfo)

	# print(Field.Mouse.factoriesAble)
	# print(Field.Mouse.factoriesGone)
	# print(Field.Mouse.factoriesWill)

	if len(Field.Mouse.factoriesGone) == 9: break
print(Field.Mouse.distance)

Submission status: Runtime Error

Solution code:
def bfs(count, x, y, cheese):
    queue = [(count,x,y)]
    while len(queue)>0:
        tempc,tempx,tempy = queue.pop(0)
        if geo[tempx][tempy] == cheese:
            return tempc,tempx,tempy
        for i in range(4):
            neox = tempx+dx[i]
            neoy = tempy+dy[i]
            if canGoTo(neox,neoy):
                queue.append((tempc+1,neox,neoy))

    return (-1,-1,-1)

def canGoTo(x,y):
    if 0<=x<H and 0<=y<W:
        return not visited[x][y]
    return False

dx = [0,1,0,-1]
dy = [-1,0,1,0]

data = input().split(' ')
H,W,N = map(int, data)

#maps
geo = [[None for i in range(W)] for j in range(H)]
visited = [[False for i in range(W)] for j in range(H)]

x,y=-1,-1
for i in range(H):
    line = input()
    for j in range(W):
        p = line[j:j+1]
        geo[i][j] = p
        if p == 'X':
            visited[i][j] = True
        elif p == 'S':
            x,y, = i,j
            
count = 0
for n in range(1,N+1):
    count,x,y = bfs(count,x,y,str(n))
print(count)