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:
# -*- 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)):
		print('current HP',current_HP)
		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: Wrong Answer

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**4):
		for cx,cy in frontier:
			if (cx,cy)==locations[current_HP]: return step+1
			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: Wrong Answer

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**4):
		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: Wrong Answer

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

    return (-1,-1,-1)

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def search(dataset):
    min_time = 0
    mouse = 1
    gx, gy = get_start(dataset)
    for i in xrange(N):
        gx, gy, min_time_tmp = bfs(dataset, (gx, gy), mouse)
        mouse += 1
        min_time += min_time_tmp
    print min_time


def bfs(dataset, start, mouse):
    INF = 10000000
    min_time = [[INF for j in xrange(W)] for i in xrange(H)]
    min_time[start[0]][start[1]] = 0
    queue = [start]

    while len(queue) != 0:
        dx, dy = queue.pop(0)
        for i, j in moves:
            nx = dx + i
            ny = dy + j
            if 0 <= nx < H and 0 <= ny < W and dataset[nx][ny] != 'X' and min_time[nx][ny] == INF:
                cell = dataset[nx][ny]
            else:
                continue
            if type(cell) is int:
                if mouse == int(cell):
                    min_time[nx][ny] = min_time[dx][dy] + 1
                    return nx, ny, min_time[nx][ny]
            min_time[nx][ny] = min_time[dx][dy] + 1
            queue.append((nx, ny))


def get_start(dataset):
    for i in xrange(H):
        rows = dataset[i]
        for j in xrange(W):
            cell = rows[j]
            if cell == 'S':
                return i, j


dataset = []
while True:
    line = raw_input().rstrip().split()
    if len(line) == 3:
        H, W, N = map(int, line)
    else:
        row = []
        for e in line[0]:
            if e.isdigit():
                row.append(int(e))
            else:
                row.append(e)
        dataset.append(row)
    if len(dataset) == H:
        print dataset
        search(dataset)
        break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def search(dataset):
    min_time = 0
    mouse = 1
    gx, gy = get_start(dataset)
    for i in xrange(N):
        gx, gy, min_time_tmp = bfs(dataset, (gx, gy), mouse)
        mouse += 1
        min_time += min_time_tmp
    print min_time


def bfs(dataset, start, mouse):
    INF = 100000000000000000
    min_time = [[INF for j in xrange(W)] for i in xrange(H)]
    min_time[start[0]][start[1]] = 0
    queue = [start]

    while len(queue) != 0:
        dx, dy = queue.pop(0)
        for i, j in moves:
            nx = dx + i
            ny = dy + j
            if 0 <= nx < H and 0 <= ny < W and dataset[nx][ny] != 'X' and min_time[nx][ny] == INF:
                cell = dataset[nx][ny]
            else:
                continue
            if type(cell) is int:
                if mouse == int(cell):
                    min_time[nx][ny] = min_time[dx][dy] + 1
                    return nx, ny, min_time[nx][ny]
            min_time[nx][ny] = min_time[dx][dy] + 1
            queue.append((nx, ny))


def get_start(dataset):
    for i in xrange(H):
        rows = dataset[i]
        for j in xrange(W):
            cell = rows[j]
            if cell == 'S':
                return i, j


dataset = []
while True:
    line = raw_input().rstrip().split()
    if len(line) == 3:
        H, W, N = map(int, line)
    else:
        row = []
        for e in line[0]:
            if e.isdigit():
                row.append(int(e))
            else:
                row.append(e)
        dataset.append(row)
    if len(dataset) == H:
        print dataset
        search(dataset)
        break

Submission status: Wrong Answer

Solution code:
field = [[4,5,2],[".","X",".",".",1],[".",".",".",".","X"],[".","X","X",".","S"],[".",2,".","X","."]]

for i in range(len(field) - 1):
    for j in range(len(field[1])):
        if field[i+1][j] == "S":
            start_x = j
            start_y = i + 1
            break
print(start_x,start_y)

def proceed(field,start_x,start_y,start_n,start_N,goal_N):
    # print("start[x]",start_x)
    # print("start[y]",start_y)
    x = [-1,0,1,0]
    y = [0,-1,0,1]
    next_x = []
    next_y = []
    next_N  = []
    # print("s_parameters",start_x,start_y,start_N,start_n,goal_N)

    for s_x,s_y,s_N in zip(start_x,start_y,start_N):
        for p_x,p_y in zip(x,y):
            if 1 <= s_y + p_y < len(field):
                #print("y",s_y + p_y)
                if 0 <= s_x + p_x < len(field[1]):
                    #print("x",s_x + p_x)
                    if field[s_y + p_y][s_x + p_x] != "X":
                        # print("x",s_x + p_x)
                        # print("y",s_y + p_y)
                        next_x.append(s_x + p_x)
                        next_y.append(s_y + p_y)
                        # print("[x]",next_x)
                        # print("[y]",next_y)
                        if field[s_y + p_y][s_x + p_x] == goal_N:
                            # print("GOAL_STATE",s_N)
                            next_N.append(s_N)
                            if s_N == goal_N:
                                # print("check",s_N,goal_N,start_N)
                                print("result",start_n + 1)
                                return  ## return None except 1
                        elif field[s_y + p_y][s_x + p_x] == s_N:
                                next_N.append(s_N + 1)
                                # print("EAT CHEESE",next_N)
                        else:
                            next_N.append(s_N)
    # print("next_N",next_N)
    next_n = start_n + 1
    proceed(field,next_x,next_y,next_n,next_N,goal_N)

proceed(field,[start_x],[start_y],0,[1],field[0][2])

Submission status: Wrong Answer

Solution code:
field = [[4,5,2],[".","X",".",".",1],[".",".",".",".","X"],[".","X","X",".","S"],[".",2,".","X","."]]

for i in range(len(field) - 1):
    for j in range(len(field[1])):
        if field[i+1][j] == "S":
            start_x = j
            start_y = i + 1
            break
# print(start_x,start_y)

def proceed(field,start_x,start_y,start_n,start_N,goal_N):
    # print("start[x]",start_x)
    # print("start[y]",start_y)
    x = [-1,0,1,0]
    y = [0,-1,0,1]
    next_x = []
    next_y = []
    next_N  = []
    # print("s_parameters",start_x,start_y,start_N,start_n,goal_N)

    for s_x,s_y,s_N in zip(start_x,start_y,start_N):
        for p_x,p_y in zip(x,y):
            if 1 <= s_y + p_y < len(field):
                #print("y",s_y + p_y)
                if 0 <= s_x + p_x < len(field[1]):
                    #print("x",s_x + p_x)
                    if field[s_y + p_y][s_x + p_x] != "X":
                        # print("x",s_x + p_x)
                        # print("y",s_y + p_y)
                        next_x.append(s_x + p_x)
                        next_y.append(s_y + p_y)
                        # print("[x]",next_x)
                        # print("[y]",next_y)
                        if field[s_y + p_y][s_x + p_x] == goal_N:
                            # print("GOAL_STATE",s_N)
                            next_N.append(s_N)
                            if s_N == goal_N:
                                # print("check",s_N,goal_N,start_N)
                                print("result",start_n + 1)
                                return  ## return None except 1
                        elif field[s_y + p_y][s_x + p_x] == s_N:
                                next_N.append(s_N + 1)
                                # print("EAT CHEESE",next_N)
                        else:
                            next_N.append(s_N)
    # print("next_N",next_N)
    next_n = start_n + 1
    proceed(field,next_x,next_y,next_n,next_N,goal_N)

proceed(field,[start_x],[start_y],0,[1],field[0][2])

Submission status: Wrong Answer

Solution code:
# field = [[3,3,1],["S",".","."],[".",".","."],[".",".",1]]

field = [[4,5,2],[".","X",".",".",1],[".",".",".",".","X"],[".","X","X",".","S"],[".",2,".","X","."]]

for i in range(len(field) - 1):
    for j in range(len(field[1])):
        if field[i+1][j] == "S":
            start_x = j
            start_y = i + 1
            break
# print(start_x,start_y)

def proceed(field,start_x,start_y,start_n,start_N,goal_N):
    # print("start[x]",start_x)
    # print("start[y]",start_y)
    x = [-1,0,1,0]
    y = [0,-1,0,1]
    next_x = []
    next_y = []
    next_N  = []
    # print("s_parameters",start_x,start_y,start_N,start_n,goal_N)

    for s_x,s_y,s_N in zip(start_x,start_y,start_N):
        for p_x,p_y in zip(x,y):
            if 1 <= s_y + p_y < len(field):
                #print("y",s_y + p_y)
                if 0 <= s_x + p_x < len(field[1]):
                    #print("x",s_x + p_x)
                    if field[s_y + p_y][s_x + p_x] != "X":
                        # print("x",s_x + p_x)
                        # print("y",s_y + p_y)
                        next_x.append(s_x + p_x)
                        next_y.append(s_y + p_y)
                        # print("[x]",next_x)
                        # print("[y]",next_y)
                        if field[s_y + p_y][s_x + p_x] == goal_N:
                            # print("GOAL_STATE",s_N)
                            next_N.append(s_N)
                            if s_N == goal_N:
                                # print("check",s_N,goal_N,start_N)
                                print(start_n + 1)
                                return  ## return None except 1
                        elif field[s_y + p_y][s_x + p_x] == s_N:
                                next_N.append(s_N + 1)
                                # print("EAT CHEESE",next_N)
                        else:
                            next_N.append(s_N)
    # print("next_N",next_N)
    next_n = start_n + 1
    proceed(field,next_x,next_y,next_n,next_N,goal_N)

proceed(field,[start_x],[start_y],0,[1],field[0][2])

Submission status: Wrong Answer

Solution code:

def getStart(field):
    search_field = field[1:]     # cut the first [H,W,N] for min_path matrix
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = []
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[[INF] * field[0][1]] for i in range(field[0][0])] #[[INF for j in range(field[0][1])] for i in range(field[0][0])]
    min_path[start_y-1][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 < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                distance += min_path[current[1]-1][current[0]] + 1
                if field[ny][nx] == gotten_cheese: # at the same cheese-power number
                    if field[ny][nx] == goal_N: # goal
                        print(distance)
                        return
                    else: # not goal, but could eat cheese
                        que = []
                        que.append([nx,ny])
                        gotten_cheese += 1
                        min_path = [[[INF] * field[0][1]] for i in range(field[0][0])]
                        min_path[ny-1][nx] = 0
                        break
                else:
                    que.append([nx,ny])


def main(field):

    # field = [[10,10,9],
    # [".","X",".",".",".","X",".","S",".","X"],
    # [6,".",".",5,"X",".",".","X",1,"X"],
    # [".",".",".","X","X","X","X",".",".","X"],
    # ["X",".",".",9,"X",".",".",".","X","."],
    # [8,".","X",2,"X",".",".","X",3,"X"],
    # [".",".",".","X","X",".","X",4,".","."],
    # ["X","X",".",".",".",".",7,"X",".","."],
    # ["X",".",".","X",".",".","X","X",".","."],
    # ["X",".",".",".","X",".","X","X",".","."],
    # [".",".","X",".",".",".",".",".",".","."]]

    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        print(matrix)
        main(matrix)
        break

Submission status: Wrong Answer

Solution code:

def getStart(field):
    search_field = field[1:]     # cut the first [H,W,N] for min_path matrix
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = []
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[INF] * field[0][1] for i in range(field[0][0])]
    min_path[start_y-1][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 < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                distance += min_path[current[1]-1][current[0]] + 1
                if field[ny][nx] == gotten_cheese: # at the same cheese-power number
                    if field[ny][nx] == goal_N: # goal
                        print(distance)
                        return
                    else: # not goal, but could eat cheese
                        que = []
                        que.append([nx,ny])
                        gotten_cheese += 1
                        min_path = [[INF] * field[0][1] for i in range(field[0][0])]
                        min_path[ny-1][nx] = 0
                        break
                else:
                    que.append([nx,ny])


def main(field):

    # field = [[10,10,9],
    # [".","X",".",".",".","X",".","S",".","X"],
    # [6,".",".",5,"X",".",".","X",1,"X"],
    # [".",".",".","X","X","X","X",".",".","X"],
    # ["X",".",".",9,"X",".",".",".","X","."],
    # [8,".","X",2,"X",".",".","X",3,"X"],
    # [".",".",".","X","X",".","X",4,".","."],
    # ["X","X",".",".",".",".",7,"X",".","."],
    # ["X",".",".","X",".",".","X","X",".","."],
    # ["X",".",".",".","X",".","X","X",".","."],
    # [".",".","X",".",".",".",".",".",".","."]]

    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        print(matrix)
        main(matrix)
        break

Submission status: Wrong Answer

Solution code:

def getStart(field):
    search_field = field[1:]     # cut the first [H,W,N] for min_path matrix
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = []
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[INF] * field[0][1] for i in range(field[0][0])]
    min_path[start_y-1][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 < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                print(min_path[current[1]-1][current[0]])
                min_path[ny-1][nx] = min_path[current[1]-1][current[0]] + 1
                if field[ny][nx] == gotten_cheese: # at the same cheese-power number
                    distance += min_path[ny-1][nx]
                    if field[ny][nx] == goal_N: # goal
                        print(distance)
                        return
                    else: # not goal, but could eat cheese
                        que = []
                        que.append([nx,ny])
                        gotten_cheese += 1
                        min_path = [[INF] * field[0][1] for i in range(field[0][0])]
                        min_path[ny-1][nx] = 0
                        break
                else:
                    que.append([nx,ny])


def main(field):
    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

# field = [[10,10,9],
# [".","X",".",".",".","X",".","S",".","X"],
# [6,".",".",5,"X",".",".","X",1,"X"],
# [".",".",".","X","X","X","X",".",".","X"],
# ["X",".",".",9,"X",".",".",".","X","."],
# [8,".","X",2,"X",".",".","X",3,"X"],
# [".",".",".","X","X",".","X",4,".","."],
# ["X","X",".",".",".",".",7,"X",".","."],
# ["X",".",".","X",".",".","X","X",".","."],
# ["X",".",".",".","X",".","X","X",".","."],
# [".",".","X",".",".",".",".",".",".","."]]
#
# main(field)

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        print(matrix)
        main(matrix)
        break

Submission status: Wrong Answer

Solution code:

def getStart(field):
    search_field = field[1:]     # cut the first [H,W,N] for min_path matrix
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = []
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[INF] * field[0][1] for i in range(field[0][0])]
    min_path[start_y-1][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 < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                print(min_path[current[1]-1][current[0]])
                min_path[ny-1][nx] = min_path[current[1]-1][current[0]] + 1
                if field[ny][nx] == gotten_cheese: # at the same cheese-power number
                    distance += min_path[ny-1][nx]
                    if field[ny][nx] == goal_N: # goal
                        print(distance)
                        return
                    else: # not goal, but could eat cheese
                        que = []
                        que.append([nx,ny])
                        gotten_cheese += 1
                        min_path = [[INF] * field[0][1] for i in range(field[0][0])]
                        min_path[ny-1][nx] = 0
                        break
                else:
                    que.append([nx,ny])


def main(field):
    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

# field = [[10,10,9],
# [".","X",".",".",".","X",".","S",".","X"],
# [6,".",".",5,"X",".",".","X",1,"X"],
# [".",".",".","X","X","X","X",".",".","X"],
# ["X",".",".",9,"X",".",".",".","X","."],
# [8,".","X",2,"X",".",".","X",3,"X"],
# [".",".",".","X","X",".","X",4,".","."],
# ["X","X",".",".",".",".",7,"X",".","."],
# ["X",".",".","X",".",".","X","X",".","."],
# ["X",".",".",".","X",".","X","X",".","."],
# [".",".","X",".",".",".",".",".",".","."]]
#
# main(field)

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        main(matrix)
        break

Submission status: Wrong Answer

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??§?????????
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 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):
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])

    # ??????????????°???(S)??¨??´????????°???(G)?????????
    sx = None                   #  ??????????????°????????§?¨?
    sy = None


    start_mark = 'S'
    for y in range(Y):
        for x in range(X):
            if field[y][x] == start_mark:
                sx = x
                sy = y
                break
        if sx != None:
            break

    total_move = 0
    for i in range(1, N+1):
        gx = None                   #  ??´????????°????????§?¨?
        gy = None
        goal_mark = str(i)

        for y in range(Y):
            for x in range(X):
                if field[y][x] == goal_mark:
                    gx = x
                    gy = y
                    break
            if gx != None:
                break
        res = bfs(field, sx, sy, gx, gy)
        total_move += res
        sx = gx
        sy = gy

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

Solution code:
print(1)

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