OD C卷 - 跳马问题

跳马问题（200）

• 输入m, n 表示一个m*n的棋盘，棋盘中存在 数字和. 两种符号，数字表示该位置的马可以走的最大步子，. 表示该位置为空；
• 马移动走“日”字，同中国象棋中的马移动；多个马可以移动到同一位置；
• 能否将棋盘上所有的马移动到同一个位置，若可以则输出最小的移动步数，若不可以输出0；

输入描述：
输入m n
输入m行数据
输出描述：
所有马移动到同一位置的最小步数，或者 0

示例1
输入：
3 2
. .
2 .
. .
输出：
0

示例2
输入：
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
输出：
17

思路：

• 马走“日”，对应八个方向
• BFS 获取每个马走到m*n棋盘中每个点的步数；
• 所有马到每个点的步数相加，取最小值 （所有马均可到的点中取步数求和的最小值）

# 马走的方向
directions = [(-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1)]
m, n = list(map(int, input().strip().split()))# result 统计 所有马 的步数之和
result = [[0 for _ in range(n)] for _ in range(m)]
# BFS 每个马到所有点走的步子数，走不到的用-1表示
matrix = [[-1 for _ in range(n)] for _ in range(m)]def init_matrix(): # 恢复为-1, 用于统计下一个马的步子数global m, n, matrixfor i in range(m):for j in range(n):matrix[i][j] = -1# 累加每个马的步子数
def update_result() :global m, n, matrix, resultfor i in range(m):for j in range(n):if matrix[i][j] == -1 or result[i][j] == -1: # 有马 无法走到该点位置 （所有马走到该位置则不可能）result[i][j] = -1 # 表示无法完成所有马到达该点else:result[i][j] += matrix[i][j]def bfs(i, j, step): # i,j起始点  step 可以走的步子数global matrix, m, nmatrix[i][j] = 0queue = [] # 队列queue.append([i, j])used_step = 1while queue and used_step <= step:size = len(queue)for k in range(size):current = queue.pop(0)for l in range(8): # 遍历走八个方向next_i = current[0] + directions[l][0]next_j = current[1] + directions[l][1]if 0 <= next_i and next_i < m and 0 <= next_j \and next_j < n and matrix[next_i][next_j] == -1:matrix[next_i][next_j] = used_stepqueue.append([next_i, next_j])used_step += 1# 输入m行数据，并BFS搜索、累加
for i in range(m):inputs = input().strip().split()for j in range(n):if inputs[j] != ".": # 有马init_matrix()bfs(i, j, int(inputs[j]))update_result()# 最终输出结果
output = float("inf")
for i in range(m):for j in range(n):if result[i][j] != -1:output = min(output, result[i][j])if output == float("inf"):print(0)
else :print(output)