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: Wrong Answer

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 = [[False] * (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(1, 10000000):
    sz = len(que)
    for loop in range(sz):
      (x,y) = popleft()
      if ss[x][y] == 'X' or not mp[x][y]:
        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 - 1
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
map(lambda x: x if x != 'S' else 0, stage)
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[int(stage[y][x])] = y
			starts_x[int(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[int(stage[y][x])-1] = y
			goals_x[int(stage[y][x])-1] = 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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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 = 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:
#! /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)]

        used = set(s)
        # print nxt
        q = [s]
        for nxt in range(1, n+1):
            # print q
            while q != []:
                y, x, ans = 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):
                        used.add((y + dy, x + dx))
                        q.append((y + dy, x + dx, ans))
                        
            q = [(y, x, ans)]
            used = set((y, x))            
            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: Accepted

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

import heapq
import sys
import re

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = map(int,input().split(" "))
r = re.compile("[0-9]")
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif r.match(char) is not None:
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

Submission status: Accepted

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

import heapq
import sys

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = map(int,input().split(" "))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

Submission status: Accepted

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

import heapq
import sys

def check_out_of_map(pos,H,W):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = map(int,input().split(" "))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

Submission status: Accepted

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__':
    inputs = (input()).split()

    H = int(inputs[0])
    W = int(inputs[1])
    N = int(inputs[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: Accepted

Solution code:
from collections import deque
r, c, n = map(int, raw_input().split())
l = [list(raw_input()) for i in range(r)]
m = [[0]*c for i in range(r)]
mv = ((0,-1),(-1,0),(0,1),(1,0))
cnt = 0
k = 1
q = deque()
for i in range(r):
    for j in range(c):
        if l[i][j] == 'S':
            q.append((j, i))
def init(x,y):
    for i in range(r):
        for j in range(c):
            if x != j or y != i: m[i][j] = 0
while (k != n+1):
    x, y = q.popleft()
    if l[y][x] == str(k):
        k+=1
        init(x,y)
        cnt = m[y][x]
        q = deque()
        q.append((x, y))
        continue
    for dx, dy in mv:
        mx = x + dx
        my = y + dy
        if mx < 0 or mx >= c or my < 0 or my >= r: continue
        if l[my][mx] == 'X': continue
        if l[my][mx] != 'X' and m[my][mx] ==0:
            m[my][mx] = m[y][x] + 1
            q.append((mx, my))
print cnt

Submission status: Accepted

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):
                #print('get')
                return temp
            if mymap[y][x] != '*':
                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]
#print(nstart)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w,n=map(int,raw_input().split())
g=[[] for _ in xrange(h)]
for i in xrange(h):
    r=raw_input()
    for j in xrange(w):
        if r[j]=="S":
             sy,sx=i,j
        g[i].append(r[j])
d=[[0]*w for i in xrange(h)]
d1=copy.deepcopy(d)
visited=[[0]*w for i in xrange(h)]
visited1=copy.deepcopy(visited)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
q=deque([[sy,sx]])
ans=0
for i in xrange(1,n+1):
    f=0
    while len(q)!=0:
        y,x=q.popleft()
        visited1[y][x]=2
        for j in xrange(4):
            nexty=y+dy[j]
            nextx=x+dx[j]
            if not check(nexty,nextx):continue
            if g[nexty][nextx]!="X" and visited1[nexty][nextx]==0:
                q.append([nexty,nextx])
                d1[nexty][nextx]=d1[y][x]+1
                visited1[nexty][nextx]=1
                if g[nexty][nextx]==str(i):
                    ans+=d1[nexty][nextx]
                    q=deque([[nexty,nextx]])
                    visited1=copy.deepcopy(visited)
                    d1=copy.deepcopy(d)
                    f=1
                    break
        if f==1:break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w,n=map(int,raw_input().split())
g=[[] for _ in xrange(h)]
for i in xrange(h):
    r=raw_input()
    for j in xrange(w):
        if r[j]=="S":
             sy,sx=i,j
        g[i].append(r[j])
d=[[0]*w for i in xrange(h)]
d1=copy.deepcopy(d)
visited=[[0]*w for i in xrange(h)]
visited1=copy.deepcopy(visited)
dx=(1,0,-1,0)
dy=(0,1,0,-1)
q=deque([(sy,sx)])
ans=0
for i in xrange(1,n+1):
    f=0
    while len(q)!=0:
        y,x=q.popleft()
        visited1[y][x]=2
        for j in xrange(4):
            nexty=y+dy[j]
            nextx=x+dx[j]
            if not check(nexty,nextx):continue
            if g[nexty][nextx]!="X" and visited1[nexty][nextx]==0:
                q.append((nexty,nextx))
                d1[nexty][nextx]=d1[y][x]+1
                visited1[nexty][nextx]=1
                if g[nexty][nextx]==str(i):
                    ans+=d1[nexty][nextx]
                    q=deque([(nexty,nextx)])
                    visited1=copy.deepcopy(visited)
                    d1=copy.deepcopy(d)
                    f=1
                    break
        if f==1:break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

x = -1
for letters in maze:
    x += 1
    y = -1
    for letter in letters:
        y += 1
        if letter == "S":
            sx = x
            sy = y
        elif letter == str(N):
            gx = x
            gy = y

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


def bfs():
    count = 0
    backup = []
    for tmp_goal in range(1, N + 1):
        d = [[INF for i in range(W)] for j in range(H)]
        if tmp_goal == 1:
            q = deque([[sx, sy]])
            d[sx][sy] = 0
        else:
            q = deque([backup])
            d[backup[0]][backup[1]] = count

        while len(q) != 0:
            tmp_x, tmp_y = q.popleft()
            if maze[tmp_x][tmp_y] == str(tmp_goal):
                count = d[tmp_x][tmp_y]
                backup = [tmp_x, tmp_y]
                q.clear()
                break
            for j in range(0, 4):
                nx = tmp_x + dx[j]
                ny = tmp_y + dy[j]
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "X" and d[nx][ny] == INF:
                    q.append([nx, ny])
                    d[nx][ny] = d[tmp_x][tmp_y] + 1
    return count


if __name__ == '__main__':
    ans = bfs()
    print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)

def calculate_distance(field,locations,current_HP):
	sx,sy = locations[current_HP-1]
	ex,ey = locations[current_HP]

	is_visit = [[False for _ in range(len(field[0]))] for __ in range(len(field))]
	is_visit[sx][sy]=True

	frontier = set()
	frontier.add(locations[current_HP-1])
	step = 0
	while not is_visit[ex][ey]:
		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
				is_visit[nx][ny] = True
				next_frontier.add((nx,ny))
		if len(next_frontier)==0: return
		frontier = next_frontier
		step += 1
	return step


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: Accepted

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

import sys
sys.setrecursionlimit(10**6)

def calculate_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 range(10**6):
		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))
		if len(next_frontier)==0: return
		frontier = next_frontier
	return -10*3

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: Accepted

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 range(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: Accepted

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 = list([locations[current_HP-1]])
	for step in range(len(field)*len(field[0])):
		next_frontier = set()
		for cx,cy in frontier:
			for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
				nx, ny = cx+dx, cy+dy
				if (nx,ny)==locations[current_HP]: return step+1
				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))
				is_visit[nx][ny] = True
		frontier = next_frontier

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