2025年【C++】怎么用深度优先算法解决扫地机器人问题？

科技前沿 • 2025-03-26 20:34 • 阅读 28

大家好，我是讯享网，很高兴认识大家。

题目描述

小麦同学为扫地机器人设计了一个在矩形区域中行走的算法。

规则如下：

采取向右 - 向下 - 向左 - 向上的路径，让扫地机器人清扫一个n*m的面积，每到一个单元格，都为其标记一个整数的到达序号，遍历过所有单元格后，机器人自动停止。

最终输出每个单元格到达的顺序编号。

举例

清扫一个3 * 4的矩形区域

3*4矩形区域
讯享网

清扫一个5 * 5的矩形区域

5*5矩形区域

输入

一行内有2个两个整数n和m，用空格隔开，分别代表矩形区域的行数（高）和列数（宽）（n和m都是2~9之间的整数）

输出

输出按题意机器人走过每个点之后，标记数字的结果，每个数字输出时场宽设置为3。

样例输入

3 4

样例输出

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

#include <bits/stdc++.h> using namespace std; int n, m; int a[20][20]; // 定义数组，存储x和y变化的值 int fx[5] = { 
   0,0,1,0,-1}; int fy[5] = { 
   0,1,0,-1,0}; // 为二维数组赋值 // 为 x，y 点赋值为 k void fun(int x, int y, int k){ 
    a[x][y] = k; // 赋值 // 优先向右，其次向下，再次向左，再次向上 // 通过循环方向值变化的数组，将x和y变化的值逐个加到x和y上 int tx, ty; // 表示将要去的点  for(int i=1; i<=4; i++){ 
    tx = x + fx[i]; ty = y + fy[i]; // 递归之前先判断，保证要访问的点的有效性 if(tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]==0){ 
    fun(tx,ty,k+1); } } } int main(){ 
    // n行m列 cin >> n >> m; // 为1,1点赋值为1 fun(1, 1, 1); // 输出 int i, j; for(i = 1; i <= n; i++){ 
    for(j = 1; j <= m; j++){ 
    cout << setw(3) << a[i][j]; } cout << endl; } }

讯享网