最新华为OD机试真题-LYA的马跳棋游戏(200分)
大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
感谢大家的订阅➕ 和 喜欢
最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
在线评测链接
LYA的马跳棋游戏(200分)
评测功能需要 =>订阅专栏<= 后联系清隆解锁～
OJ题目截图
LYA的马跳棋游戏
问题描述
LYA最近迷上了一款马跳棋游戏。游戏在一个 行 列的棋盘上进行,棋盘上有若干个等级不同的马。每匹马的走法与中国象棋中的马相同,即走"日"字:先横着或竖着走一格,再斜着走一格。等级为 的马可以连续跳 到 步,但不能跳出棋盘。
LYA想知道,能否将所有的马跳到同一个格子上?如果可以,最少需要多少步?
注意:
- 允许多匹马在跳跃过程中到达同一个格子。
- 坐标为 的马可以跳到 、、、、、、、 这八个格子中的任意一个,前提是不能跳出棋盘。
输入格式
第一行包含两个正整数 和 ,表示棋盘的行数和列数。
接下来 行,每行包含 个字符。若第 行第 列的字符为 '.',表示这个格子是空的;若为数字 ,表示这里有一匹等级为 的马。
输出格式
输出一个整数,表示将所有马跳到同一格子所需的最少总步数。若无法做到,则输出 。
样例输入
3 2
..
2.
..
样例输出
0
样例解释
棋盘上只有一匹马,它不需要跳。
样例输入
3 5
47.48
4744.
7....
样例输出
17
数据范围
题解
本题可以用多源BFS来解决。基本思路如下:
-
对每匹马所在的位置进行BFS,计算该马跳到棋盘上每个格子的最少步数。这一步可以预处理出每匹马跳到每个格子的距离。
-
枚举棋盘上所有格子,对于每个格子,计算所有马跳到该格子的总步数。在所有可能的目标格子中,总步数最少的就是答案。
具体实现时,可以把棋盘压缩成一维,方便进行BFS。另外,由于棋盘上可能有多达 个格子,所以每次BFS时需要传入起点坐标,以便在 dist 数组中进行标记。
预处理完所有马的距离后,枚举每个格子,计算所有马跳到该格子的距离之和。如果发现有马无法跳到该格子,则总距离直接设为无穷大。最后,在所有格子中找出总距离最小的,就是答案。
时间复杂度 ,空间复杂度 。其中 和 分别为棋盘的行数和列数。
参考代码
- Python
from collections import deque
N = 30
g = [[''] * N for _ in range(N)]
n, m = 0, 0
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [-2, 2, -2, 2, -1, 1, -1, 1]
dist = {}
def bfs(x, y, u, k):
q = deque([(x, y)])
dist[u][x][y] = 0
while q:
x1, y1 = q.popleft()
for i in range(8):
x2, y2 = x1 + dx[i], y1 + dy[i]
if 0 <= x2 < n and 0 <= y2 < m and dist[u][x2][y2] > dist[u][x1][y1] + 1 and dist[u][x1][y1] < k:
dist[u][x2][y2] = dist[u][x1][y1] + 1
q.append((x2, y2))
def main():
global n, m, g, dist
n, m = map(int, input().split())
pos = []
for i in range(n):
line = input()
for j in range(m):
u = i * m + j
dist[u] = [[0x3f3f3f3f] * m for _ in range(n)]
g[i][j] = line[j]
if '1' <= g[i][j] <= '9':
bfs(i, j, u, int(g[i][j]))
pos.append((i, j))
ans = 0x3f3f3f3f
for i in range(n):
for j in range(m):
cnt = 0
for p in pos:
u = p[0] * m + p[1]
if dist[u][i][j] == 0x3f3f3f3f:
cnt = 0x3f3f3f3f
break
cnt += dist[u][i][j]
ans = min(ans, cnt)
if ans == 0x3f3f3f3f:
print("-1")
else:
print(ans)
if __name__ == "__main__":
main()
- Java
import java.util.*;
public class Main {
static final int N = 30;
static final int INF = 0x3f3f3f3f;
static char[][] g = new char[N]