深搜与回溯——扫地机器人问题解析与代码实现
一、题目内容
题目描述
扫地机器人在一个 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()) # 初始化一个 (n+1)×(m+1) 的二维数组，用于存储清扫顺序 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='') # 格式化输出，宽度为3 print() # 换行四、代码运行逻辑
初始化网格：创建一个大小为 (n+1)×(m+1) 的二维数组
a，并初始化所有值为 0。多出的一行和一列用于简化边界条件的判断。递归函数
fun：
标记当前位置的清扫顺序。
按照“右、下、左、上”的顺序尝试移动。
如果某个方向可以移动（即目标位置未被清扫），则递归调用
fun。递归终止条件：当四个方向都无法移动时，递归结束。
输出结果：格式化输出网格，每个位置的值表示清扫顺序。
五、运行结果示例
输入：
3 4输出：
复制
1 2 3 4 8 9 10 5 7 6 11 12解释：
机器人从 (1,1) 开始，依次向右移动，清扫顺序为 1, 2, 3, 4。
无法向右移动时，向下移动，清扫顺序为 5。
继续向左移动，清扫顺序为 6, 7, 8。
继续向下移动，清扫顺序为 9, 10。
最后向上移动，清扫顺序为 11, 12。
六、总结
这道题考察了深度优先搜索（DFS）的实现，以及递归的使用。通过模拟机器人的移动规则，我们可以高效地生成清扫顺序。代码中通过递归实现了四个方向的优先级判断，并通过二维数组存储了清扫顺序。希望这篇文章能帮助你更好地理解和解决类似问题。
原文地址：https://blog.csdn.net/m0_73581472/article/details/145269348
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！