深搜与回溯——扫地机器人问题解析与代码实现

一、题目内容

题目描述
扫地机器人在一个 n×m 的网格中从左上角（1,1）开始清扫。它按照以下规则移动：

1. 如果当前位置的右边（同一行，下一列）没有被清扫过，它会向右移动。

2. 如果右边无法移动，则向下移动。

3. 如果右边和下方都无法移动，则尝试向左移动。

4. 如果左边也无法移动，则尝试向上移动。

5. 如果四个方向都无法移动，则停止清扫。

要求输出清扫完成后的网格，其中每个位置的值表示机器人清扫该位置的顺序。

输入：
两个整数 n 和 m，表示网格的行数和列数（1≤n,m≤100）。

输出：
一个 n×m 的网格，每个位置的值表示机器人清扫该位置的顺序。

样例：
输入：

3 4

输出：

  1   2   3   4
  8   9  10   5
  7   6  11  12

二、问题分析

1. 问题本质：这是一个经典的“深度优先搜索”（DFS）问题，机器人按照特定规则在网格中移动，类似于“螺旋矩阵”的生成。

2. 移动规则：机器人优先向右移动，其次向下、向左、向上。这可以通过递归实现，每次递归时检查四个方向是否可以移动。

3. 终止条件：当机器人无法向任何方向移动时，递归结束。

4. 数据结构：使用二维数组 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='')  # 格式化输出，宽度为3print()  # 换行

四、代码运行逻辑

1. 初始化网格：创建一个大小为 (n+1)×(m+1) 的二维数组 a，并初始化所有值为 0。多出的一行和一列用于简化边界条件的判断。

2. 递归函数 fun：

   • 标记当前位置的清扫顺序。

   • 按照“右、下、左、上”的顺序尝试移动。

   • 如果某个方向可以移动（即目标位置未被清扫），则递归调用 fun。

3. 递归终止条件：当四个方向都无法移动时，递归结束。

4. 输出结果：格式化输出网格，每个位置的值表示清扫顺序。

五、运行结果示例

输入：

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）的实现，以及递归的使用。通过模拟机器人的移动规则，我们可以高效地生成清扫顺序。代码中通过递归实现了四个方向的优先级判断，并通过二维数组存储了清扫顺序。希望这篇文章能帮助你更好地理解和解决类似问题。