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:
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):
			ny = y + move_y[i]
			nx = x + move_x[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


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 + [0,1,0,-1][i]
			nx = x + [1,0,-1,0][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


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 (data_y) and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			ny = y + [0,1,0,-1][i]
			nx = x + [1,0,-1,0][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:
#import time, sys#
from collections import deque

H, W, N = map(int, input().split())
field = [list(input()) for i in range(H)]
'''
20 30 9
.......X..8.XXXX.XX..XX.X.XX..
X.XX....X.XX..X.X.X....XXXX..X
..X.X..XX..X.....XX.X..X.XX...
....X.X.X.XXX.X..X..X.X..XX.X.
..XXX.XX...X.X....X.X..X..X...
..X...........X.X...X.1.XX...X
.X.X....X..XX..XX......9.X...4
..X....X........X......X......
....XXX.X...XX.X.....X.X..X.X.
..S..XXX..X....X.X.......X..X.
.5...XX..X.X..X....X...XXX....
..X...X.X....X....X..X.2X.....
XXXXXXXX.X.XX..XX..XX.......X.
.....X...........3..XX.XXX.X.X
..X.....X..X..XX.XX..X.X...XX.
...X..X.XXX.XX......X...X..XXX
.X.XX.X.........X.X...X...X..X
..X...X..X..XX..XXX..X.XX...X.
X....X.X....X...X.X..XX.XX..X.
...X6X..X........X.X.....7.X..
'''

#input = input().split('\n')#
#H, W, N = map(int, input.pop(0).split())#
#field = [line for line in input]#
node_posi = [0 for i in range(N+1)]

#s1 = time.time()#
nodes = 'S123456789'
for i in range(H):
	for j in range(W):
		if field[i][j] in nodes:
			node_posi[nodes.index(field[i][j])] = [j, i]
#e1 = time.time()#
#print("b:{}".format(e1-s1))#

cost = 0
#count = 1#
for i in range(len(node_posi)-1):
	#s2 = time.time()#
	searched = [[-1]*W for i in range(H)]
	start, goal = node_posi[i], node_posi[i+1]
	Q = deque([start])
	searched[start[1]][start[0]] = 0
	goal_flag = False
	
	while Q and not goal_flag:
		x, y = Q.popleft()
		goal_flag = False

		for q in range(4):
			nx = x + [1,0,-1,0][q]
			ny = y + [0,1,0,-1][q]
			
			if nx >= 0 and nx < W and ny >= 0 and ny < H:
				if searched[ny][nx] == -1 and field[ny][nx] != 'X':
					Q.append([nx, ny])
					searched[ny][nx] = searched[y][x] + 1
					if ([nx, ny] == goal):
						cost += searched[ny][nx]
						goal_flag = True
						break

			#s = "\n".join(["".join(map(lambda x: str(x)[:1], j)) for j in searched])#
			#sys.stdout.write("\r{}".format(s))#
			#sys.stdout.flush()#
	
	#e2 = time.time()#
	#print("{}:{}".format(count, e2-s2))#
	#count += 1#
print(cost)

Submission status: Accepted

Solution code:
from collections import deque

H, W, N = map(int, input().split())
field = [list(input()) for i in range(H)]
node_posi = [0 for i in range(N+1)]

nodes = 'S123456789'
for i in range(H):
	for j in range(W):
		if field[i][j] in nodes:
			node_posi[nodes.index(field[i][j])] = [j, i]

cost = 0
for i in range(len(node_posi)-1):
	searched = [[-1]*W for i in range(H)]
	start, goal = node_posi[i], node_posi[i+1]
	Q = deque([start])
	searched[start[1]][start[0]] = 0
	goal_flag = False
	
	while Q and not goal_flag:
		x, y = Q.popleft()
		goal_flag = False

		for q in range(4):
			nx = x + [1,0,-1,0][q]
			ny = y + [0,1,0,-1][q]
			
			if nx >= 0 and nx < W and ny >= 0 and ny < H:
				if searched[ny][nx] == -1 and field[ny][nx] != 'X':
					Q.append([nx, ny])
					searched[ny][nx] = searched[y][x] + 1
					if ([nx, ny] == goal):
						cost += searched[ny][nx]
						goal_flag = True
						break

print(cost)

Submission status: Accepted

Solution code:
from collections import deque
H,W,N=map(int,input().split())
e='X'*(W+2)
M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
m=(1,-1,W+2,-W-2)
def f(s,g):
 p,t=s,0
 q=deque()
 b=[1]*len(M);b[s]=0
 while 1:
  for d in m:
   n=p+d
   if'X'!=M[n]and b[n]:
    if M[n]==g:return(n,t+1)
    b[n]=0;q.append([n,t+1])
  p,t=q.popleft()
s=M.find('S')
a=0
for i in range(1,N+1):
 s,t=f(s,str(i))
 a+=t
print(a)

Submission status: Accepted

Solution code:
def v():
 from collections import deque
 H,W,N=map(int,input().split())
 e='X'*(W+2)
 M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
 m=(1,-1,W+2,-W-2)
 def f(s,g):
  p,t=s,0
  q=deque()
  b=[1]*len(M);b[s]=0
  while 1:
   for d in m:
    n=p+d
    if'X'!=M[n]and b[n]:
     if M[n]==g:return(n,t+1)
     b[n]=0;q.append([n,t+1])
   p,t=q.popleft()
 s=M.find('S')
 a=0
 for i in range(1,N+1):
  s,t=f(s,str(i))
  a+=t
 print(a)
if'__main__'==__name__:v()

Submission status: Accepted

Solution code:
def v():
 import sys
 from collections import deque
 H,W,N=map(int,input().split())
 e='X'*(W+2)
 M=e+''.join('X'+e[:-1]+'X'for e in sys.stdin)+e
 m=(1,-1,W+2,-W-2)
 def f(s,g):
  p,t=s,0
  q=deque()
  b=[1]*len(M);b[s]=0
  while 1:
   for d in m:
    n=p+d
    if'X'!=M[n]and b[n]:
     if M[n]==g:return(n,t+1)
     b[n]=0;q.append([n,t+1])
   p,t=q.popleft()
 s=M.find('S')
 a=0
 for i in range(1,N+1):
  s,t=f(s,str(i))
  a+=t
 print(a)
if'__main__'==__name__:v()

Submission status: Accepted

Solution code:
def v():
 from collections import deque
 H,W,N=map(int,input().split())
 e='X'*(W+2)
 M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
 m=(1,-1,W+2,-W-2)
 def f(s,g):
  p,t=s,0
  q=deque()
  b=[1]*len(M);b[s]=0
  while 1:
   for d in m:
    n=p+d
    if'X'!=M[n]and b[n]:
     if M[n]==g:return(n,t+1)
     b[n]=0;q.append([n,t+1])
   p,t=q.popleft()
 s=M.find('S')
 a=0
 for i in range(1,N+1):
  s,t=f(s,str(i))
  a+=t
 print(a)
v()

Submission status: Accepted

Solution code:
import copy

(h, w, n) = list(map(int, input().split()))
dis = [[] for i in range(n + 1)]


def setArr(ph):
    global dis
    res = [False for i in range(w + 2)]
    for i, x in enumerate(list(input())):
        if x == "X":
            continue
        res[i + 1] = True
        if x == ".":
            continue
        if x == "S":
            dis[0] = [ph, i + 1]
            continue
        dis[int(x)] = [ph, i + 1]
    return res


arr = [[] for i in range(h + 2)]
arr[0] = [False for i in range(w + 2)]
arr[-1] = [False for i in range(w + 2)]
for i in range(1, h + 1):
    arr[i] = setArr(i)

res = 0
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def ze(start, goal):
    arra = copy.deepcopy(arr)
    global res
    queue = [start, [-1, -1]]
    ap = queue.append
    zu = False
    for q in queue:
        if q[0] < 1:
            res += 1
            ap([-1, -1])
            continue
        if not arra[q[0]][q[1]]:
            continue
        for m in move:
            de = [q[0] + m[0], q[1] + m[1]]

            if de == goal:
                res += 1
                zu = True
                break
            if arra[de[0]][de[1]]:
                ap(de)
        if zu:
            break
        arra[q[0]][q[1]] = False


for i in range(n):
    ze(dis[i], dis[i + 1])

print(res)

Submission status: Accepted

Solution code:
from collections import deque

h, w, n = map(int, input().split())
g = ['0'] * h

sx, sy = -1, -1
pos = -1
for i in range(h):
    g[i] = input()
    if pos == -1:
        pos = g[i].find('S')
        if pos != -1:
            sx = i
            sy = pos

book = set()
queue = deque()

ans = 0

Next = [[-1, 0], [1, 0], [0, -1], [0, 1]]

for a in range(1, n + 1):
    book.clear()
    queue.clear()
    queue.append((sx, sy, 0))
    aim = str(a)

    while len(queue):
        t = queue.popleft()
        if (t[0], t[1]) in book:
            continue

        if g[t[0]][t[1]] == aim:
            ans += t[2]
            # print(t[0], ' ', t[1], ' ', aim, ' ', ans)
            sx, sy = t[0], t[1]
            break

        book.add((t[0], t[1]))
        for i in range(4):
            tx = t[0] + Next[i][0]
            ty = t[1] + Next[i][1]
            if 0 <= tx < h and 0 <= ty < w and g[tx][ty] != 'X':
                queue.append((tx, ty, t[2] + 1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

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

G = []

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


Q = deque()
Q.append((sx, sy, 0))
visited = defaultdict(lambda: defaultdict(int))
visited[sx][sy] = 1

target = '1'

while len(Q):
    x, y, step = Q.popleft()
    if G[x][y] == target:
        visited.clear()
        Q.clear()
        target = str(int(target) + 1)
        if target == str(N + 1):
            print(step)
            break
    for dx, dy in d:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and G[nx][ny] != 'X':
            if not visited[nx][ny]:
                visited[nx][ny] = 1
                Q.append((nx, ny, step + 1))

Submission status: Accepted

Solution code:
from collections import deque

def getStartPos(cmap,H,W):
    for y in range(H):
        for x in range(W):
            if cmap[y][x]=="S":
                return x,y

mv=((1,0),(-1,0),(0,1),(0,-1))
H,W,N=map(int,raw_input().split())
cmap=[list(raw_input()) for i in range(H)]
sx,sy=getStartPos(cmap,H,W)
Q=deque()
Q.append((sx,sy,0,0,1))
visited=set()
visited.add((sx,sy))
while Q:
    x,y,t,n,p=Q.popleft()
    if n==N:
        print t
        break
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>=W or my<0 or my>=H:
            continue
        if cmap[my][mx]=="X":
            continue
        if (mx,my) not in visited:
            visited.add((mx,my))
            Q.append((mx,my,t+1,n,p))
        if cmap[my][mx]==str(p):
            visited=set()
            visited.add((mx,my))
            Q=deque()
            Q.append((mx,my,t+1,n+1,p+1))
            break

Submission status: Accepted

Solution code:
from Queue import Queue
INF = 20000000
q = Queue()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
smp = [[INF for i in range(1002)] for j in range(1002)]
mp = [['X' for i in range(1002)] for j in range(1002)]
H, W, n = map(int,raw_input().split())
for i in range(1, H+1):
    ipt = raw_input()
    for j in range(1, W+1):
        mp[i][j] = ipt[j-1];
x = y = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if mp[i][j]=='S':
            x = j; y = i;
c = 0; ans = 0;
q.put([x,y]); smp[y][x] = 0;
while c<n:
    p = q.get()
    x = p[0]; y = p[1];
    if mp[y][x]==chr(ord('1')+c):
        ans += smp[y][x]; c+=1;
        if c==n: break;
        while q.empty()==False: q.get()
        for i in range(1, H+1):
            for j in range(1, W+1):
                smp[i][j] = INF
        smp[y][x] = 0
    for i in range(4):
        if mp[y+dy[i]][x+dx[i]]!='X' and smp[y+dy[i]][x+dx[i]]==INF:
            q.put([x+dx[i], y+dy[i]]);
            smp[y+dy[i]][x+dx[i]] = smp[y][x]+1;
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W,N = map(int,input().split())
graph = []
S = None
for i in range(H):
  row = list(input())
  if "S" in row:
    s = row.index("S")
    S = (i,s)
  graph.append(row)

def bfs(S, target):
  q = deque([S])
  visited = set()
  step = 0

  while q:
    l = len(q)
    next_q = deque()

    for _ in range(l):
      r,c = q.popleft()
      if graph[r][c] == str(target):
        return step, r, c
      visited.add((r,c))

      for x,y in [(1,0), (0,1), (-1,0), (0,-1)]:
        nr,nc = r+x,c+y
        if nr<0 or nc<0 or nr>=H or nc>=W: continue
        if (nr,nc) in visited: continue
        if (nr,nc) in next_q: continue
        if graph[nr][nc] == target:
          return step+1, nr, nc
        if graph[nr][nc] != "X":
          next_q.append((nr,nc))

    step += 1
    q = next_q

res = 0
for i in range(1, N+1):
  steps, x,y = bfs(S, i)
  S = (x,y)
  res += steps
  # print(i, steps, (x,y))

print(res)

Submission status: Accepted

Solution code:
import sys
import collections
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 7

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, N = ZZ()
    field = [input() for _ in range(H)]
    D = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(start, goal):
        dist = [[INF] * W for _ in range(H)]
        deq = collections.deque()
        sx, sy = start
        dist[sx][sy] = 0
        deq.append([sx, sy])

        while deq:
            x, y = deq.popleft()
            for dx, dy in D:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and field[nx][ny] != 'X' and dist[nx][ny] == INF:
                    dist[nx][ny] = dist[x][y] + 1
                    deq.append([nx, ny])
        return dist[goal[0]][goal[1]]

    factory = [[] for _ in range(N+1)]
    for i in range(H):
        for j in range(W):
            if field[i][j] == 'S': factory[0] = [i, j]
            elif field[i][j] in {'1', '2', '3', '4', '5', '6', '7', '8', '9'}:
                factory[int(field[i][j])] = [i, j]
    ans = 0
    for i in range(N): ans += bfs(factory[i], factory[i+1])
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def clear(self):
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v, sach_v):
        # 初期条件(0-indexed)
        self.dist[start_v] = 0
        self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                if self.val[next_v] == 'X':
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)
                if self.val[next_v] == sach_v:
                    return self.dist[next_v]


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H,W,N   = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    cnt = 0
    start_v_arr = ['S']+[str(i) for i in range(1,N+1)]
    for i, start_v in enumerate(start_v_arr[:-1]):
        bfs.clear()
        for v,val in enumerate(g_val):
            if val == start_v:
                cnt += bfs.bfs(v,start_v_arr[i+1])
                break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
graph = [list(input()) for _ in range(H)]
from collections import deque


def bfs_gird(start, x_lim=H, y_lim=W):
    seen = {start}
    todo = deque()
    todo.append(start)
    dis = {start: 0}

    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while todo:
        x, y, level = todo.popleft()
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not ((0 <= nx < x_lim) and (0 <= ny < y_lim)):
                continue
            if (nx, ny, level) in seen:
                continue
            elif graph[nx][ny] == "X":
                continue
            elif graph[nx][ny] == str(N) and level==N-1:
                return dis[(x, y, level)] + 1
            elif graph[nx][ny] == str(level+1):
                nxy = (nx, ny, level+1)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)
            else:
                nxy = (nx, ny, level)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)
        del dis[(x, y, level)]
def finds():
    for i in range(H):
        for j in range(W):
            if graph[i][j] == "S":
                return (i, j, 0)

ans = bfs_gird(finds())
print(ans)

Submission status: Accepted

Solution code:
import collections
INF = 10**18
h,w,n = map(int,input().split())
li = [list(input()) for i in range(h)]
num = [0]*9
def bfs(sy,sx,gy,gx):
    d = [[INF]*w for i in range(h)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d[sy][sx] = 0
    que = collections.deque([])
    que.append((sy,sx))
    while que:
        y,x = que.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=nx<w and 0<=ny<h:
                if li[ny][nx] != "X" and d[ny][nx] == INF:
                    que.append((ny,nx))
                    d[ny][nx] = d[y][x] + 1
    return d[gy][gx]

for i in range(h):
    for j in range(w):
        if li[i][j] == "S":
            sy = i
            sx = j
        if li[i][j] == "1":
            gy = i
            gx = j
        elif li[i][j] == "2":
            num[1] = [i,j]
        elif li[i][j] == "3":
            num[2] = [i,j]
        elif li[i][j] == "4":
            num[3] = [i,j]
        elif li[i][j] == "5":
            num[4] = [i,j]
        elif li[i][j] == "6":
            num[5] = [i,j]
        elif li[i][j] == "7":
            num[6] = [i,j]
        elif li[i][j] == "8":
            num[7] = [i,j]
        elif li[i][j] == "9":
            num[8] = [i,j]
ans = bfs(sy,sx,gy,gx)
num[0] = [gy,gx]
for i in range(n-1):
    sy,sx = num[i]
    gy,gx = num[i+1]
    ans += bfs(sy,sx,gy,gx)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
from queue import Queue
sys.setrecursionlimit(100000)

Delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = sys.maxsize

def bfs(start, target):
    d = [[INF] * w for i in range(h)]
    
    queue = Queue()
    queue.put(start)
    d[start[1]][start[0]] = 0

    while (queue.qsize()):
        p = queue.get()

        for delta in Delta:
            dx = p[0] + delta[0]
            dy = p[1] + delta[1]
            if not (0 <= dx and dx < w and 0 <= dy and dy < h):
                continue

            value = matrix[dy][dx]

            if value.isdigit() and value == target:
                return d[p[1]][p[0]] + 1, (dx, dy)

            if value != "X" and d[dy][dx] == INF:
                if value == "." or value == "S" or value.isdigit():
                    queue.put((dx, dy))
                    d[dy][dx] = d[p[1]][p[0]] + 1

    
def findStart(matrix):
    for j, row in enumerate(matrix):
        for i, cell in enumerate(row):
            if cell == "S":
                return (i, j)    

while (True):
    line = sys.stdin.readline().rstrip()
    if line == "":
        break

    h, w, c = (int(i) for i in line.split())

    matrix = []
    count = 0
    for i in range(h):
        matrix.append(list(input().rstrip()))
    
                
    start = findStart(matrix)
    for i in range(1, c+1):
        res, start = bfs(start, str(i))
        count += res 

    print(count)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


diff_row = [-1,0,0,1]
diff_col = [0,-1,1,0]

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

def rangeCheck(row,col):
    global H,W
    return row >= 0 and row <= H-1 and col >= 0 and col <= W-1

loc = [None]*(N+1)

base_map = [input() for _ in range(H)]
for row in range(H):
    for col in range(W):
        if base_map[row][col] in ["." ,"X"]:
            continue
        if base_map[row][col] == "S":
            loc[0] = (row,col)
        else:
            loc[int(base_map[row][col])] = (row,col)

ans = 0
for i in range(N):
    start_row,start_col = loc[i]
    goal_row,goal_col = loc[i+1]
    table = [[BIG_NUM]*W for _ in range(H)]

    table[start_row][start_col] = 0
    Q = deque()
    Q.append((start_row,start_col))

    while len(Q) > 0:
        tmp_row,tmp_col = Q.popleft()

        if tmp_row == goal_row and tmp_col == goal_col:
            ans += table[goal_row][goal_col] #重みは全て1なので、最短経路は最初にgoalに到達するはず
            break

        for k in range(4):
            adj_row = tmp_row+diff_row[k]
            adj_col = tmp_col+diff_col[k]
            if rangeCheck(adj_row, adj_col) == False or base_map[adj_row][adj_col] == "X"  \
                    or table[adj_row][adj_col] <= table[tmp_row][tmp_col]+1:
                continue
            table[adj_row][adj_col] = table[tmp_row][tmp_col]+1
            Q.append((adj_row,adj_col))

print("%d"%(ans))

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
    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:
from copy import deepcopy
from collections import deque

H, W, N = map(int, input().split())
town = [list(input()) for i in range(H)]

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = deque()
stamina = 1
town_tmp = deepcopy(town)

for i in range(H):
    for j in range(W):
        if town[i][j] == 'S':
            queue.append((i, j, 0))
            town_tmp[i][j] = 'X'

while True:
    i, j, time = queue.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W:
            if town_tmp[ni][nj] == str(stamina):
                stamina += 1
                if stamina == N + 1:
                    print(time+1)
                    exit()
                town_tmp = deepcopy(town)
                queue = deque()
                queue.append((ni, nj, time+1))
                break
            elif town_tmp[ni][nj] == 'X':
                continue
            else:
                queue.append((ni, nj, time+1))
                town_tmp[ni][nj] = 'X'

Submission status: Accepted

Solution code:
r,c,n=map(int,input().split())
grid=[input() for _ in [0]*r]
visit=[[grid[i][j]=="X" for j in range(c)] for i in range(r)]
cheese=[None for _ in [0]*(n+1)]

for i in range(r):
    for j in range(c):
        if grid[i][j] in ("X","."):
            continue
        elif grid[i][j]=="S":
            cheese[0]=[i,j]
        else:
            cheese[int(grid[i][j])]=[i,j]
cnt=0

for p in range(n):
    aa,bb=cheese[p]
    cc,dd=cheese[p+1]
    q=[[aa,bb]]
    v=[[visit[i][j] for j in range(c)] for i in range(r)]
    v[aa][bb]=True
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    flag=False
    while q:
        qq=[]
        while q:
            i,j=q.pop()
            for dx,dy in d:
                if 0<=i+dx<r and 0<=j+dy<c:
                    if i+dx==cc and j+dy==dd:
                        flag=True
                    if v[i+dx][j+dy]==False:
                        v[i+dx][j+dy]=True
                        qq.append([i+dx,j+dy])
        q=qq
        cnt+=1
        if flag==True:
            break
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

def solve(board, start, end, W, H):

    check = [[False for j in range(W + 2)] for i in range(H + 2)]
    q = deque()
    t = (start[0], start[1], 0)
    q.append(t)
    while True:
        p = q.popleft()
        x = p[0]
        y = p[1]
        g = p[2]
        if (x, y) == end:

            return g

        if check[y][x]:
            continue
        else:
            check[y][x] = True

        if not board[y - 1][x] == 'X':
            q.append((x, y - 1, g + 1))
        if not board[y + 1][x] == 'X':
            q.append((x, y + 1, g + 1))
        if not board[y][x - 1] == 'X':
            q.append((x - 1, y, g + 1))
        if not board[y][x + 1] == 'X':
            q.append((x + 1, y, g + 1))


def main():
    H, W, N = map(int, input().split())

    board = [['X' for j in range(W + 2)] for i in range(H + 2)]
    number = 'S123456789'
    place = [(0, 0)] * (N + 1)
    for i in range(H):
        s = input()
        for j in range(W):
            board[i + 1][j + 1] = s[j]
            if s[j] in number:
                place[number.index(s[j])] = (j + 1, i + 1)

    ans = 0
    for i in range(N):
        ans += solve(board, place[i], place[i + 1], W, H)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

w+=2
G=[list('X'*w)]
for i in range(h):
    G+=[list('X'+input()+'X')]
G+=[list('X'*w)]
h+=2

def bfs(sx,sy,gx,gy):
    que=deque()
    g=[[float('inf')]*w for _ in range(h)]
    g[sx][sy]=0
    que.append((sx,sy))
    xy=[(0,-1),(-1,0),(1,0),(0,1)]

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if G[nx][ny]!='X' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1
    return g[gx][gy]


res=0

goals=[(0,0) for i in range(n+1)]

for i in range(1,h):
    for j in range(1,w):
        if G[i][j]=='S':
            goals[0]=(i,j)
        if G[i][j].isdecimal():
            num=int(G[i][j])
            goals[num]=(i,j)

for i in range(len(goals)-1):
    sx,sy=goals[i][0],goals[i][1]
    gx,gy=goals[i+1][0],goals[i+1][1]
    
    res+=bfs(sx,sy,gx,gy)

print(res)