题目分析：清洁机器人路径规划问题

这是一个典型的多目标路径规划问题，结合了图论中的最短路径和旅行商问题（TSP）的特点。核心任务是为机器人规划一条覆盖所有脏砖块（'*'）的最短路径，同时避开障碍物（'x'）。

关键约束条件

1. 地图规模：最大 20×20 网格（w, h ≤ 20）
2. 脏砖块数量：不超过 10 个（'*'）
3. 移动规则：机器人每次只能移动到相邻四方向（上、下、左、右）的网格
4. 重复访问：允许重复访问网格，但脏砖块访问后即变干净
5. 不可达情况：若存在无法到达的脏砖块，输出 -1

问题特性

• NP-Hard 问题：本质是带约束的 TSP 问题（需遍历多个目标点）
• 状态空间压缩：利用脏砖块数量少（≤10）的特性降低复杂度
• 双层规划：
  • 底层：计算任意两点间最短路径（BFS）
  • 上层：求解访问所有脏砖块的最优顺序（DFS/状态压缩DP）

解题思路：分层优化策略

步骤 1：预处理关键点

1. 收集关键点坐标：
   • 机器人起点（'o'）→ 标记为索引 0
   • 所有脏砖块（'*'）→ 标记为索引 1~k（k ≤ 10）
   • 存储到数组 point[] 并建立坐标→索引的映射 tag[][]

步骤 2：计算关键点间的最短路径

1. BFS 计算点对距离：
   • 对每个关键点（包括起点）执行 BFS
   • 得到距离矩阵 dis[i][j] 表示关键点 i → j 的最短步数
   • 注意：BFS 需避开障碍物（'x'）

步骤 3：可达性检查

• 遍历距离矩阵 dis[][]：
  • 若存在 dis[i][j] = ∞（不可达），直接输出 -1
  • 确保所有关键点连通

步骤 4：求解最优访问顺序

1. 问题转化：

   • 起点固定（索引 0）
   • 需遍历所有脏砖块（索引 1~k）
   • 求访问全部脏砖块的最短路径和 → TSP 问题

2. DFS + 回溯求解：

   • 状态：当前点索引 pos，已访问点数 step，当前总步数 sum
   • 剪枝：当前 sum > ans 时回溯
   • 终止条件：访问所有脏砖块（step == cnt）

步骤 5：输出结果

• 若存在可行解：输出 ans（最小步数）
• 否则输出 -1

代码示例

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stdio.h>
using namespace std;
char mp[50][50];
int dis[50][50];
int vis[50][50];
int tag[50][50];
const int inf = 99999999;
struct node
{
    int x, y, step;
}point[500];
int w, h, cnt, ans;
void bfs(node fir, int pt)
{
    queue <node > s;
    fir.step = 0;
    while (!s.empty())
        s.pop();
    vis[fir.x][fir.y] = 1;
    s.push(fir);
    while (!s.empty())
    {
        node t = s.front();
        s.pop();
        if (mp[t.x][t.y] == '*' || mp[t.x][t.y] == 'o')
            dis[pt][tag[t.x][t.y]] = t.step;
        int next[4][2] = { 0,1,0,-1,1,0,-1,0 };
        for (int i = 0; i < 4; i++)
        {
            node temp = t;
            temp.x += next[i][0];
            temp.y += next[i][1];
            if (temp.x<1 || temp.y<1 || temp.x>h || temp.y>w || vis[temp.x][temp.y] == 1 || mp[temp.x][temp.y] == 'x')
            {
                continue;
            }
            temp.step += 1;
            s.push(temp);
            vis[temp.x][temp.y] = 1;
        }

    }
}
int vist[50];
void dfs(int x, int step, int s)
{
    if (step == cnt)
    {
        ans = min(s, ans);
        return;
    }
    if (s > ans)
        return;
    for (int i = 1; i <= cnt; i++)
    {
        if (vist[i])
            continue;
        vist[i] = 1;
        dfs(i, step + 1, s + dis[x][i]);
        vist[i] = 0;
    }
}

int main()
{
    while (~scanf("%d%d", &w, &h))
    {
        if (w == 0 && h == 0)
            break;
        cnt = 0;
        getchar();
        memset(point, 0, sizeof(point));
        memset(tag, 0, sizeof(tag));
        memset(dis, 0, sizeof(dis));
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                scanf("%c", &mp[i][j]);
                if (mp[i][j] == '*')
                {
                    point[++cnt].x = i;
                    point[cnt].y = j;
                    tag[i][j] = cnt;
                }
                else if (mp[i][j] == 'o')
                {
                    tag[i][j] = 0;
                    point[0].x = i;
                    point[0].y = j;
                }
            }
            getchar();
        }
        /*for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
                cout<<mp[i][j];
            cout<<endl;
        }
        cout<<"xxxx"<<endl;*/
        for (int i = 0; i <= cnt; i++)
        {
            for (int j = 0; j <= cnt; j++)
            {
                if (i != j)
                    dis[i][j] = inf;
                else
                    dis[i][j] = 0;
            }
        }
        for (int i = 0; i <= cnt; i++)
        {
            memset(vis, 0, sizeof(vis));
            bfs(point[i], i);
        }
        /*  for(int i=0;i<=cnt;i++)
          {
              for(int j=0;j<=cnt;j++)
                  cout<<dis[i][j]<<" ";
              cout<<endl;
          }*/
        bool flag = 1;
        for (int i = 0; i <= cnt && flag; i++)
            for (int j = 0; j <= cnt && flag; j++)
                if (dis[i][j] == inf)
                    flag = 0;
        if (!flag)
        {
            printf("-1\n");
            continue;
        }
        memset(vist, 0, sizeof(vist));
        vist[0] = 1;
        ans = inf;
        dfs(0, 0, 0);
        printf("%d\n", ans);

    }
}

复杂度分析

注：k 为脏砖块数量，w、h 为地图尺寸