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:
def bfs(field,H,W,start_x,start_y,tmp_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    que = []
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[INF] * W for i in range(H)]
    min_path[start_y][start_x] = 0
    while len(que) != 0:
        current = que.pop(0)
        for d in direction:
            nx = current[0] + d[0]
            ny = current[1] + d[1]
            if 0 <= nx < W and 0 <= ny < H and field[ny][nx] != "X" and min_path[ny][nx] == INF:
                min_path[ny][nx] = min_path[current[1]][current[0]] + 1
                if field[ny][nx] == tmp_N:
                    return nx,ny,min_path[ny][nx]
                else:
                    que.append([nx,ny])

def getField():
    matrix = []
    first = input().strip()
    H,W,N = map(int,first.split())
    for i in range(H):
        row = list(input().strip())
        for j in range(W):
            if row[j].isdigit():
                row[j] = int(row[j])
        matrix.append(row)
    return matrix,H,W,N

def getStart(field):
    for y in range(len(field)):
        for x in range(len(field[0])):
            if field[y][x] == "S":
                return x,y

def main():
    matrix,H,W,N = getField()
    sx,sy = getStart(matrix)
    distance = 0
    tmp_x,tmp_y,tmp_dist = bfs(matrix,H,W,sx,sy,1)
    distance += tmp_dist
    tmps = [tmp_x,tmp_y]
    for k in range(N-1):
        tmp_x,tmp_y,tmp_dist = bfs(matrix,H,W,tmps[0],tmps[1],k+2)
        distance += tmp_dist
        tmps = [tmp_x,tmp_y]
    print(distance)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import queue
class unko(Exception):pass
INF=1145141919
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def search(cor_s,dst):
    mem=[[INF for i in range(a[1])]for j in range(a[0])]
    q=queue.Queue()
    q.put(cor_s)
    mem[cor_s[0]][cor_s[1]]=0
    while not q.empty():
        cor=q.get()
        for i in range(4):
            x=cor[0]+dx[i]
            y=cor[1]+dy[i]
            if 0<=x<a[0] and 0<=y<a[1] and s[x][y]!='X' and mem[x][y]==INF:
                mem[x][y]=mem[cor[0]][cor[1]]+1
                if s[x][y]==str(dst):return [[x,y],mem[x][y]]
                else:q.put([x,y])
#
a=[int(num)for num in input().split(' ')]
s=[list(input()) for i in range(a[0])]
pos_s=[]
time=0
for li in s:
    if 'S' in li:pos_s=[s.index(li),li.index('S')]
for i in range(a[2]):
    ret_l=search(pos_s,i+1)
    pos_s=ret_l[0]
    time+=ret_l[1]
print(time)

Submission status: Accepted

Solution code:
#import queue #queue
INF=1145141919
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def search(cor_s,dst):
    mem=[[INF for i in range(a[1])]for j in range(a[0])]
    #q=queue.Queue() #queue
    #q.put(cor_s) #queue
    li=[cor_s] #list
    mem[cor_s[0]][cor_s[1]]=0
    #while not q.empty(): #queue
    while len(li)!=0: #list
        #cor=q.get() #queue
        cor=li.pop(0) #list
        for i in range(4):
            x=cor[0]+dx[i]
            y=cor[1]+dy[i]
            if 0<=x<a[0] and 0<=y<a[1] and s[x][y]!='X' and mem[x][y]==INF:
                mem[x][y]=mem[cor[0]][cor[1]]+1
                if s[x][y]==str(dst):return [[x,y],mem[x][y]]
                else:
                    #q.put([x,y]) #queue
                    li.append([x,y])
#
a=[int(num)for num in input().split(' ')]
s=[list(input()) for i in range(a[0])]
pos_s=[]
time=0
for li in s:
    if 'S' in li:pos_s=[s.index(li),li.index('S')]
for i in range(a[2]):
    ret_l=search(pos_s,i+1)
    pos_s=ret_l[0]
    time+=ret_l[1]
print(time)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(field, sx, sy, gx, gy):
    # ????????????????§????????????´????????§?¨??????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????

    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])

    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0               #  ??????????????°??????????????????0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        if cx == gx and cy == gy:
            break
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (0 <= nx < X) and (0 <= ny < Y) and field[ny][nx] != 'X' and d[ny][nx] == float('inf'):
                Q.append((nx, ny))
                d[ny][nx] = d[cy][cx] + 1
    return d[gy][gx]


def find_mark(data):
    founds = []
    if 'S' in data:
        founds.append(['S', data.index('S')])
    if '1' in data:
        founds.append(['1', data.index('1')])
    if '2' in data:
        founds.append(['2', data.index('2')])
    if '3' in data:
        founds.append(['3', data.index('3')])
    if '4' in data:
        founds.append(['4', data.index('4')])
    if '5' in data:
        founds.append(['5', data.index('5')])
    if '6' in data:
        founds.append(['6', data.index('6')])
    if '7' in data:
        founds.append(['7', data.index('7')])
    if '8' in data:
        founds.append(['8', data.index('8')])
    if '9' in data:
        founds.append(['9', data.index('9')])
    return founds

def solve(field, N):
    # ??????????????°???(S)??¨??´????????°???(G)?????????
    pos = [[None, None] for _ in range(N+1)]
    for y, row in enumerate(field):
        res = find_mark(row)
        for mark, x in res:
            if mark is not None:
                if mark == 'S':
                    pos[0] = [x, y]
                else:
                    pos[int(mark)] = [x, y]

    total_move = 0
    start = pos[0]
    for goal in pos[1:]:
        sx, sy = start
        gx, gy = goal
        res = bfs(field, sx, sy, gx, gy)
        # print('From: ({}, {}) -> To: ({}, {}), step: {}'.format(sx, sy, gx, gy, res))
        # print('min move: {}'.format(abs(sx-gx) + abs(sy-gy)))
        total_move += res
        start = goal

    return total_move


def main(args):
    # N = 9
    # data = [
    #     '.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.......'
    # ]
    H, W, N = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
AC
"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(field, sx, sy, gx, gy):
    """
    ??????????????°???????????´????????°????????§????????¢????±???????
    :param field:
    :param sx: ??????????????°????????§?¨?
    :param sy:
    :param gx: ??´????????°????????§?¨?
    :param gy:
    :return: ????????????????????´???????????§????????¢
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0               #  ??????????????°??????????????????0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        if cx == gx and cy == gy:
            break
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (0 <= nx < X) and (0 <= ny < Y) and field[ny][nx] != 'X' and d[ny][nx] == float('inf'):
                Q.append((nx, ny))
                d[ny][nx] = d[cy][cx] + 1
    return d[gy][gx]


def solve(field, N):
    # ??????????????°???(S)??¨??´????????°???(N)?????????
    pos = [[None, None] for _ in range(N+1)]
    for y, row in enumerate(field):
        for mark in 'S123456789':
            if mark in row:
                if mark == 'S':
                    pos[0] = [row.index(mark), y]
                else:
                    pos[int(mark)] = [row.index(mark), y]

    total_move = 0
    start = pos[0]
    for goal in pos[1:]:
        sx, sy = start
        gx, gy = goal
        res = bfs(field, sx, sy, gx, gy)
        # print('From: ({}, {}) -> To: ({}, {}), step: {}'.format(sx, sy, gx, gy, res))
        # print('min move: {}'.format(abs(sx-gx) + abs(sy-gy)))
        total_move += res
        start = goal

    return total_move


def main(args):
    # N = 9
    # data = [
    #     '.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.......'
    # ]
    H, W, N = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
AC
"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline
from collections import defaultdict

def bfs(field, sx, sy, gx, gy):
    """
    ??????????????°???????????´????????°????????§????????¢????±???????
    :param field:
    :param sx: ??????????????°????????§?¨?
    :param sy:
    :param gx: ??´????????°????????§?¨?
    :param gy:
    :return: ????????????????????´???????????§????????¢
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    # d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    d = defaultdict(int)

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    Q.append((sx, sy))
    d['{:04d}{:04d}'.format(sy, sx)] = 0               #  ??????????????°??????????????????0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        if cx == gx and cy == gy:
            break
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (0 <= nx < X) and (0 <= ny < Y) and field[ny][nx] != 'X' and '{:04d}{:04d}'.format(ny, nx) not in d:
                Q.append((nx, ny))
                d['{:04d}{:04d}'.format(ny, nx)] = d['{:04d}{:04d}'.format(cy, cx)] + 1
    return d['{:04d}{:04d}'.format(gy, gx)]


def solve(field, N):
    # ??????????????°???(S)??¨??´????????°???(N)?????????
    pos = [[None, None] for _ in range(N+1)]
    for y, row in enumerate(field):
        for mark in 'S123456789':
            if mark in row:
                if mark == 'S':
                    pos[0] = [row.index(mark), y]
                else:
                    pos[int(mark)] = [row.index(mark), y]

    total_move = 0
    start = pos[0]
    for goal in pos[1:]:
        sx, sy = start
        gx, gy = goal
        res = bfs(field, sx, sy, gx, gy)
        # print('From: ({}, {}) -> To: ({}, {}), step: {}'.format(sx, sy, gx, gy, res))
        # print('min move: {}'.format(abs(sx-gx) + abs(sy-gy)))
        total_move += res
        start = goal

    return total_move


def main(args):
    # N = 9
    # data = [
    #     '.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.......'
    # ]
    H, W, N = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import collections

def search(sy, sx, gy, gx):
    visited = [[False for j in range(W)] for i in range(H)]
    visited[sy][sx] = True
 
    dq = collections.deque()
    dq.append((0, sy, sx))
    while dq:
        cost, y, x = dq.popleft()
        if (y,x) == (gy, gx):
            return cost
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if visited[ny][nx] or cells[ny][nx] == 'X':
                continue
            dq.append((cost + 1, ny, nx))
            visited[ny][nx] = True

def main(H, W, N, cells):
    points = {}
    for i in range(H):
        for j in range(W):
            points[cells[i][j]] = (i, j)
    points['0'] = points['S']
    total = 0
    for i in range(1, N+1):
        sy, sx = points[str(i-1)]
        gy, gx = points[str(i)]
        total += search(sy, sx, gy, gx)
    print(total)
 
 
if __name__ == '__main__':
    H, W, N = map(int, input().split())

    cells = []
    for i in range(H):
        cells.append(input())
    main(H, W, N, cells)

Submission status: Accepted

Solution code:
import collections


def search(sy, sx, gy, gx):
    visited = [[False for j in range(W)] for i in range(H)]
    visited[sy][sx] = True

    dq = collections.deque()
    dq.append((0, sy, sx))
    while dq:
        cost, y, x = dq.popleft()
        if (y, x) == (gy, gx):
            return cost
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if visited[ny][nx] or cells[ny][nx] == 'X':
                continue
            dq.append((cost + 1, ny, nx))
            visited[ny][nx] = True


def main(H, W, N, cells):
    points = {}
    for i in range(H):
        for j in range(W):
            points[cells[i][j]] = (i, j)
    points['0'] = points['S']
    total = 0
    for i in range(1, N + 1):
        sy, sx = points[str(i - 1)]
        gy, gx = points[str(i)]
        total += search(sy, sx, gy, gx)
    print(total)


if __name__ == '__main__':
    H, W, N = map(int, input().split())

    cells = []
    for i in range(H):
        cells.append(input())
    main(H, W, N, cells)

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

H, W, N = map(int, file_input.readline().split())

town_map = file_input.read()

start_index = town_map.index('S')

mouse = [start_index, 0]
# position, elapsed time

from collections import deque

for goal in range(1, N + 1):
    q = deque()
    unvisited = [True] * len(town_map)
    unvisited[mouse[0]] = False
    goal = str(goal)
    while True:
        cur_pos = mouse[0]
        
        ew_pos = cur_pos % (W + 1)
        if ew_pos < (W - 1):
            next_pos = cur_pos + 1
            lot = town_map[next_pos]
            if lot != 'X' and unvisited[next_pos]:
                if lot == goal:
                    mouse = [next_pos, mouse[1] + 1]
                    break
                else:
                    m = [next_pos, mouse[1] + 1]
                    unvisited[next_pos] = False
                    q.append(m)
        if ew_pos > 0:
            next_pos = cur_pos - 1
            lot = town_map[next_pos]
            if lot != 'X' and unvisited[next_pos]:
                if lot == goal:
                    mouse = [next_pos, mouse[1] + 1]
                    break
                else:
                    m = [next_pos, mouse[1] + 1]
                    unvisited[next_pos] = False
                    q.append(m)
        
        ns_pos = cur_pos // (W + 1)
        if ns_pos < (H - 1):
            next_pos = cur_pos + W + 1
            lot = town_map[next_pos]
            if lot != 'X' and unvisited[next_pos]:
                if lot == goal:
                    mouse = [next_pos, mouse[1] + 1]
                    break
                else:
                    m = [next_pos, mouse[1] + 1]
                    unvisited[next_pos] = False
                    q.append(m)
        if ns_pos > 0:
            next_pos = cur_pos - W - 1
            lot = town_map[next_pos]
            if lot != 'X' and unvisited[next_pos]:
                if lot == goal:
                    mouse = [next_pos, mouse[1] + 1]
                    break
                else:
                    m = [next_pos, mouse[1] + 1]
                    unvisited[next_pos] = False
                    q.append(m)
        mouse = q.popleft()

print(mouse[1])

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

H, W, N = map(int, file_input.readline().split())

town_map = 'X' * (W + 2)
for line in file_input:
    town_map += 'X' + line.rstrip() + 'X'
town_map += 'X' * (W + 2)

move = (1, -1, W + 2, -W - 2)

from collections import deque

def search(start_pos, goal_lot):
    mouse = [start_pos, 0] # position, elapsed time
    q = deque()
    unvisited = [True] * len(town_map)
    unvisited[start_pos] = False
    goal_lot
    while True:
        cur_pos = mouse[0]
        for d in move:
            next_pos = cur_pos + d
            lot = town_map[next_pos]
            if lot != 'X' and unvisited[next_pos]:
                if lot == goal_lot:
                    return (next_pos, mouse[1] + 1)
                else:
                    m = [next_pos, mouse[1] + 1]
                    unvisited[next_pos] = False
                    q.append(m)
        mouse = q.popleft()

def solve():
    start_pos = town_map.find('S')
    time = 0
    for i in range(1, N + 1):
        start_pos, t = search(start_pos, str(i))
        time += t
    print(time)

solve()

Submission status: Accepted

Solution code:
def step(cheese):
    global x, y, a, d
    gone = set()
    q = [(x, y)]
    steps = 1
    while True:
        nq = []
        for i in q:
            for j in range(4):
                xy = (i[0] + d[j][0], i[1] + d[j][1])
                if a[xy[1]][xy[0]] == cheese:
                    x, y = xy
                    return steps
                elif xy not in gone and a[xy[1]][xy[0]] != "X":
                    gone.add(xy)
                    nq.append(xy)
        q = nq
        steps += 1

h, w, n = map(int, input().split())
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
a = ["X" * (w + 2)]
for _ in range(h):
    a.append("X" + input() + "X")
a.append("X" * (w + 2))
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j] == "S":
            x, y = j, i
            
steps = 0
for i in range(1, n + 1):        
    steps += step(str(i))
print(steps)

Submission status: Accepted

Solution code:
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
    for x in range(w):
        if stage[y][x] in starts:
            starts_y[starts.index(stage[y][x])] = y
            starts_x[starts.index(stage[y][x])] = x
        if stage[y][x] in goals:
            goals_y[goals.index(stage[y][x])] = y
            goals_x[goals.index(stage[y][x])] = x

move_y = [1,-1,0,0]
move_x = [0,0,1,-1]
sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
    bfs_map = [[-1 for j in range(w)] for i in range(h)]
    data_y = [start_y]
    data_x = [start_x]
    bfs_map[start_y][start_x] = 0
    goal = False

    while len(data_y) != 0 and not goal:
        y = data_y.pop(0)
        x = data_x.pop(0)
        goal = False

        for i in range(4):
            y += move_y[i]
            x += move_x[i]

            if y >= 0 and y < h and x >= 0 and x < w:
                if bfs_map[y][x] == -1 and stage[y][x] != "X":
                    bfs_map[y][x] = bfs_map[y-move_y[i]][x-move_x[i]]+1
                    data_y.append(y)
                    data_x.append(x)
                if bfs_map[goal_y][goal_x] != -1:
                    sum += bfs_map[goal_y][goal_x]
                    goal = True
                    break
            y -= move_y[i]
            x -= move_x[i]

print(sum)

Submission status: Accepted

Solution code:
import queue
from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(1,n + 1):
    if str(j) in s:
      factrys[j] = (i + 1, s.index(str(j)))
  ss.append(s)
ss.append("X" * (w + 2))

def bfs(i):
  mp = [[None] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  mp[x][y] = 0
  que = queue.Queue()
  que.put((x, y))
  while True:
    (x,y) = que.get()
  #  print(i,x,y)
  #  print(mp[x][y])
    if (x,y) == factrys[i + 1]:
      return mp[x][y]
    count = mp[x][y]
    if ss[x + 1][y] != "X" and mp[x + 1][y] is None:
      mp[x + 1][y] = count + 1
      que.put((x + 1, y))
    if ss[x - 1][y] != "X" and mp[x - 1][y] is None:
      mp[x - 1][y] = count + 1
      que.put((x - 1, y))
    if ss[x][y + 1] != "X" and mp[x][y + 1] is None:
      mp[x][y + 1] = count + 1
      que.put((x, y + 1))
    if ss[x][y - 1] != "X" and mp[x][y - 1] is None:
      mp[x][y - 1] = count + 1
      que.put((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += (ret)
print(ans)

Submission status: Accepted

Solution code:
import queue
from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(1,n + 1):
    if str(j) in s:
      factrys[j] = (i + 1, s.index(str(j)))
  ss.append(s)
ss.append("X" * (w + 2))

def bfs(i):
  mp = [[None] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  mp[x][y] = 0
  que = deque()
  que.append((x, y))
  while True:
    (x,y) = que.popleft()
  #  print(i,x,y)
  #  print(mp[x][y])
    if (x,y) == factrys[i + 1]:
      return mp[x][y]
    count = mp[x][y]
    if ss[x + 1][y] != "X" and mp[x + 1][y] is None:
      mp[x + 1][y] = count + 1
      que.append((x + 1, y))
    if ss[x - 1][y] != "X" and mp[x - 1][y] is None:
      mp[x - 1][y] = count + 1
      que.append((x - 1, y))
    if ss[x][y + 1] != "X" and mp[x][y + 1] is None:
      mp[x][y + 1] = count + 1
      que.append((x, y + 1))
    if ss[x][y - 1] != "X" and mp[x][y - 1] is None:
      mp[x][y - 1] = count + 1
      que.append((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += (ret)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
append = ss.append
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(len(s)):
    if s[j] != 'S' and s[j] != '.' and s[j] != 'X':
      factrys[int(s[j])] = (i + 1, j)
  append(s)
append("X" * (w + 2))

def bfs(i):
  mp = [[None] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  mp[x][y] = 0
  que = deque()
  append = que.append
  popleft = que.popleft
  append((x, y))
  while True:
    (x,y) = popleft()
  #  print(i,x,y)
  #  print(mp[x][y])
    if (x,y) == factrys[i + 1]:
      return mp[x][y]
    count = mp[x][y]
    if ss[x + 1][y] != "X" and mp[x + 1][y] is None:
      mp[x + 1][y] = count + 1
      append((x + 1, y))
    if ss[x - 1][y] != "X" and mp[x - 1][y] is None:
      mp[x - 1][y] = count + 1
      append((x - 1, y))
    if ss[x][y + 1] != "X" and mp[x][y + 1] is None:
      mp[x][y + 1] = count + 1
      append((x, y + 1))
    if ss[x][y - 1] != "X" and mp[x][y - 1] is None:
      mp[x][y - 1] = count + 1
      append((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += (ret)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
append = ss.append
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(len(s)):
    if s[j] != 'S' and s[j] != '.' and s[j] != 'X':
      factrys[int(s[j])] = (i + 1, j)
  append(s)
append("X" * (w + 2))

def bfs(i):
  mp = [[None] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  que = deque()
  append = que.append
  popleft = que.popleft
  append((x, y))
  for count in range(10000000):
    sz = len(que)
    for loop in range(sz):
      (x,y) = popleft()
      if ss[x][y] == 'X' or not mp[x][y] is None:
        continue
      if (x,y) == factrys[i + 1]:
        return count
      mp[x][y] = count
      append((x + 1, y))
      append((x - 1, y))
      append((x, y + 1))
      append((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += (ret)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
append = ss.append
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(len(s)):
    if s[j] != 'S' and s[j] != '.' and s[j] != 'X':
      factrys[int(s[j])] = (i + 1, j)
  append(s)
append("X" * (w + 2))

def bfs(i):
  mp = [[-1] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  que = deque()
  append = que.append
  popleft = que.popleft
  append((x, y))
  for count in range(10000000):
    sz = len(que)
    for loop in range(sz):
      (x,y) = popleft()
      if ss[x][y] == 'X' or not mp[x][y] is -1:
        continue
      if (x,y) == factrys[i + 1]:
        return count
      mp[x][y] = count
      append((x + 1, y))
      append((x - 1, y))
      append((x, y + 1))
      append((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += (ret)
print(ans)

Submission status: Accepted

Solution code:
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
	for x in range(w):
		if stage[y][x] in starts:
			starts_y[starts.index(stage[y][x])] = y
			starts_x[starts.index(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[goals.index(stage[y][x])] = y
			goals_x[goals.index(stage[y][x])] = x


sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
	bfs_map = [[-1 for j in range(w)] for i in range(h)]
	data_y = [start_y]
	data_x = [start_x]
	bfs_map[start_y][start_x] = 0
	goal = False
	
	while len(data_y) != 0 and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			ny = y + [1,-1,0,0][i]
			nx = x + [0,0,1,-1][i]
			
			if ny >= 0 and ny < h and nx >= 0 and nx < w:
				if bfs_map[ny][nx] == -1 and stage[ny][nx] != "X":
					bfs_map[ny][nx] = bfs_map[y][x]+1
					data_y.append(ny)
					data_x.append(nx)
			if bfs_map[goal_y][goal_x] != -1:
				sum += bfs_map[goal_y][goal_x]
				goal = True
				break

print(sum)

Submission status: Accepted

Solution code:
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
	for x in range(w):
		if stage[y][x] in starts:
			starts_y[starts.index(stage[y][x])] = y
			starts_x[starts.index(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[goals.index(stage[y][x])] = y
			goals_x[goals.index(stage[y][x])] = x

move_y = [1,-1,0,0]
move_x = [0,0,1,-1]
sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
	bfs_map = [[-1 for j in range(w)] for i in range(h)]
	data_y = [start_y]
	data_x = [start_x]
	bfs_map[start_y][start_x] = 0
	goal = False
	
	while len(data_y) != 0 and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			y += move_y[i]
			x += move_x[i]
			
			if y >= 0 and y < h and x >= 0 and x < w:
				if bfs_map[y][x] == -1 and stage[y][x] != "X":
					bfs_map[y][x] = bfs_map[y-move_y[i]][x-move_x[i]]+1
					data_y.append(y)
					data_x.append(x)
				if bfs_map[goal_y][goal_x] != -1:
					sum += bfs_map[goal_y][goal_x]
					goal = True
					break
			y -= move_y[i]
			x -= move_x[i]

print(sum)