题意，n行m列的地图，‘ . '，代表可以走的道路，' o ',你的初始位置，‘ x ' 墙，' * ',垃圾，也就是你要去的地方，你的任务是找到一条最短路径来清理垃圾，若没有这条路，则输出-1，多组输入
思路
据说是TSP然而我不会，据说可以状压DP，然而我是DP白痴，那怎么办，暴搜呗
第一步，存图，读图很容易，但是我们需要将起点和所有垃圾的位置记录下来，方便搜索用，下面讲怎么用
第二步，建图，因为我们需要找一条路来到所有点，所以这不是单源最短路，跑最短路的小伙伴注意了，我们用刚刚记录起点和垃圾位置的数组来跑若干遍BFS，求出起点和垃圾到图中其他点的最短路，然后判断是否存在一个垃圾不能到其他垃圾或起点，若果有，那么就要输出-1
第三步，暴搜，暴搜只需要搜你的存点的数组中的点就好，把其他点抽象成你的两个点之间的路径，使图中只剩下起点和垃圾，每次搜索传3个参，当前点的标号，已经清理了几个垃圾，当前路径长，当当前层搜索的花费大于之前某次搜索到的最小花费，则return，当前层无意义，若所有垃圾清理完了，那么比较当前花费与记录的最小花费的大小（其实已经保证肯定当前搜到的最小，为啥自己看代码），更新路径的最小值
代码
By Acer.Mo #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int INF=10000000; int h,l,stx,sty,st,cnt=1,ans=INF; int jud[500]; int dis[500][500]; int point[500];//存点 struct zb { int x,y; }qaq[500];//存垃圾与起点的坐标 struct bfss { int x; int y; int cost; bool friend operator < (bfss a,bfss b) { return a.cost>b.cost; } };//跑最短路用 char map[100][100]; int ask(int a,int b) { return a*l+b; }//返回标号 void bfs(int emm) { int vis[500][500]={0};//记得定在外面要清空 bfss now,t; int fx[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; priority_queue<bfss>q; now.x=qaq[emm].x;now.y=qaq[emm].y;now.cost=0; vis[now.x][now.y]=1; q.push(now); while (q.size())//正常跑 { now=q.top();q.pop(); dis[ask(now.x,now.y)][emm]=dis[emm][ask(now.x,now.y)]=now.cost;//更新当前点与bfs（x）的最短路 for (int i=0;i<4;i++) { t.x=now.x+fx[i][0]; t.y=now.y+fx[i][1]; t.cost=now.cost+1; if (map[t.x][t.y]=='x'||vis[t.x][t.y]||t.x<0||t.y<0||t.x>=h||t.y>=l) continue;//不合法 q.push(t); vis[t.x][t.y]=1; } } return ; } int dfs(int poi,int num,int cost)//标号，数量，花费 { if (num==0||cost>ans)//上面说的，保证一定会小，因为不小于就return { ans=min(cost,ans); return 0; } for (int i=1;i<cnt;i++)//0存的起点，不需要搜索，只需要枚举每个垃圾就好 { if (jud[point[i]]) continue; jud[point[i]]=1; dfs(point[i],num-1,cost+dis[poi][point[i]]); jud[point[i]]=0; } return 0; } bool built()//构图 { for (int i=0;i<cnt;i++)for (int k=0;k<cnt;k++) dis[point[i]][point[k]]=INF;//重置 for (int i=0;i<cnt;i++) { bfs(point[i]);//每个点到其他点的dis for (int k=i+1;k<cnt;k++) { if (dis[point[i]][point[k]]==INF) return 0;//有不能到的 } } return 1; } int main() { while (~scanf("%d %d",&l,&h)&&h&&l) { fill(jud,jud+500,0);cnt=1;ans=INF;//判断有没有用过，dfs用的 for (int i=0;i<h;i++) scanf("%s",map[i]); for (int i=0;i<h;i++) { for (int k=0;k<l;k++) { if (map[i][k]=='o') { point[0]=ask(i,k);st=ask(i,k);//看清point下标固定为零 qaq[ask(i,k)].x=i,qaq[ask(i,k)].y=k;//存入 } else if (map[i][k]=='*') { point[cnt++]=ask(i,k); qaq[ask(i,k)].x=i,qaq[ask(i,k)].y=k; } } } int flag=built(); if (!flag) { puts("-1"); continue; } jud[st]=1; dfs(st,cnt-1,0); printf("%d\n",ans); } return 0; }