跳马
题目描述
输入 m 和 n 两个数, m 和 n 表示一个 m*n 的棋盘. 输入棋盘内的数据. 棋盘中存在数字和.
两种字符, 如果是数字表示该位置是一匹马, 如果是.表示该位置为空的, 棋盘内的数字表示为该马能走的最大步数.
例如棋盘内某个位置一个数字为 k, 表示该马只能移动 1~k 步的距离.
棋盘内的马移动类似于中国象棋中的马移动, 先在水平或者垂直方向上移动一格, 然后再将其移动到对角线位置.
棋盘内的马可以移动到同一个位置, 同一个位置可以有多匹马.
请问能否将棋盘上所有的马移动到同一个位置, 若可以请输入移动的最小步数. 若不可以输出 0.
输入描述
输入 m 和 n 两个数, m 和 n 表示一个 m*n 的棋盘. 输入棋盘内的数据. 棋盘中存在数字和.
两种字符, 如果是数字表示该位置是一匹马, 如果是 .表示该位置为空的, 棋盘内的数字表示为该马能走的最大步数.
例如棋盘内某个位置一个数字为 k, 表示该马只能移动 1~k 步的距离.
棋盘内的马移动类似于中国象棋中的马移动, 先在水平或者垂直方向上移动一格, 然后再将其移动到对角线位置.
棋盘内的马可以移动到同一个位置, 同一个位置可以有多匹马.
请问能否将棋盘上所有的马移动到同一个位置, 若可以请输入移动的最小步数, 若不可以输出 0.
输出描述
能否将棋盘上所有的马移动到同一个位置, 若可以请输入移动的最小步数, 若不可以输出 0.
示例1
输入:
3 2
. .
2 .
. .
输出:
0
示例2
输入:
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
输出:
17
题解
Python
from collections import deque
def main():
# 读取行列值
rows, columns = list(map(int, input().split()))
horse_matrix = []
for row in range(rows):
parts = input().split()
for column in range(columns):
if parts[column] != ".":
# 马可以移动的最大步数
steps = int(parts[column])
horse_matrix.append((row, column, steps))
# 可以移动的方向
directions = ((-1, -2), (-1, 2), (1, -2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1))
INITIAL_STEPS = 10 ** 9
def dfs(row, column, x, y, max_move_steps, dist, visited):
if row == x and column == y:
return dist
# 访问所有的方向
for dx, dy in directions:
x2 = x + dx
y2 = y + dy
# 检查新的坐标位置是否有效, 是否访问过
if 0 <= x2 < rows and 0 <= y2 < columns and dist < max_move_steps and (x2, y2) not in visited:
visited.add((x2, y2))
steps = dfs(row, column, x2, y2, max_move_steps, dist + 1, visited)
if steps > -1:
return steps
return -1
min_steps = INITIAL_STEPS
# 遍历每个位置
for row in range(rows):
for column in range(columns):
# 所有马移动的总步数
total_steps = 0
possible_move = True
# 遍历每只马
for x, y, move_steps in horse_matrix:
visited = set()
steps = dfs(row, column, x, y, move_steps, 0, visited)
print("steps:", steps)
if steps > -1:
total_steps += steps
break
else:
possible_move = False
if possible_move:
print("total steps:", total_steps)
min_steps = min(min_steps, total_steps)
print("min_steps:", min_steps)
if __name__ == "__main__":
main()