js模板网站,企业网站定位,建设集团有限公司,小程序与app一、题目内容 题目描述 扫地机器人在一个 nm 的网格中从左上角#xff08;1,1#xff09;开始清扫。它按照以下规则移动#xff1a; 如果当前位置的右边#xff08;同一行#xff0c;下一列#xff09;没有被清扫过#xff0c;它会向右移动。 如果右边无法移动#xf…一、题目内容 题目描述 扫地机器人在一个 n×m 的网格中从左上角1,1开始清扫。它按照以下规则移动 如果当前位置的右边同一行下一列没有被清扫过它会向右移动。 如果右边无法移动则向下移动。 如果右边和下方都无法移动则尝试向左移动。 如果左边也无法移动则尝试向上移动。 如果四个方向都无法移动则停止清扫。 要求输出清扫完成后的网格其中每个位置的值表示机器人清扫该位置的顺序。 输入 两个整数 n 和 m表示网格的行数和列数1≤n,m≤100。 输出 一个 n×m 的网格每个位置的值表示机器人清扫该位置的顺序。 样例 输入 3 4 输出 1 2 3 4 8 9 10 5 7 6 11 12 二、问题分析 问题本质这是一个经典的“深度优先搜索”DFS问题机器人按照特定规则在网格中移动类似于“螺旋矩阵”的生成。 移动规则机器人优先向右移动其次向下、向左、向上。这可以通过递归实现每次递归时检查四个方向是否可以移动。 终止条件当机器人无法向任何方向移动时递归结束。 数据结构使用二维数组 a 来存储每个位置的清扫顺序。 三、代码解析 以下是代码的详细解析 # 输入网格的行数和列数
n, m map(int, input().split())# 初始化一个 (n1)×(m1) 的二维数组用于存储清扫顺序
a [[0 for i in range(m 1)] for i in range(n 1)]def fun(x, y, z):递归函数模拟机器人的清扫过程。:param x: 当前行:param y: 当前列:param z: 当前清扫顺序a[x][y] z # 标记当前位置的清扫顺序# 向右移动优先级最高if y 1 m and a[x][y 1] 0:fun(x, y 1, z 1)# 向下移动elif x 1 n and a[x 1][y] 0:fun(x 1, y, z 1)# 向左移动elif y - 1 1 and a[x][y - 1] 0:fun(x, y - 1, z 1)# 向上移动elif x - 1 1 and a[x - 1][y] 0:fun(x - 1, y, z 1)# 从左上角 (1,1) 开始清扫初始清扫顺序为 1
fun(1, 1, 1)# 输出清扫完成后的网格
for i in range(1, n 1):for j in range(1, m 1):print({: 3}.format(a[i][j]), end) # 格式化输出宽度为3print() # 换行 四、代码运行逻辑 初始化网格创建一个大小为 (n1)×(m1) 的二维数组 a并初始化所有值为 0。多出的一行和一列用于简化边界条件的判断。 递归函数 fun 标记当前位置的清扫顺序。 按照“右、下、左、上”的顺序尝试移动。 如果某个方向可以移动即目标位置未被清扫则递归调用 fun。 递归终止条件当四个方向都无法移动时递归结束。 输出结果格式化输出网格每个位置的值表示清扫顺序。 五、运行结果示例 输入 3 4 输出 复制 1 2 3 48 9 10 57 6 11 12 解释 机器人从 (1,1) 开始依次向右移动清扫顺序为 1, 2, 3, 4。 无法向右移动时向下移动清扫顺序为 5。 继续向左移动清扫顺序为 6, 7, 8。 继续向下移动清扫顺序为 9, 10。 最后向上移动清扫顺序为 11, 12。 六、总结 这道题考察了深度优先搜索DFS的实现以及递归的使用。通过模拟机器人的移动规则我们可以高效地生成清扫顺序。代码中通过递归实现了四个方向的优先级判断并通过二维数组存储了清扫顺序。希望这篇文章能帮助你更好地理解和解决类似问题。
