当前位置：首页 > news >正文

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

news 2025/7/21 17:25:29

一、题目内容

题目描述
扫地机器人在一个 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='')  # 格式化输出，宽度为3print()  # 换行
四、代码运行逻辑

初始化网格：创建一个大小为 (n+1)×(m+1) 的二维数组 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。