POJ 2688 Clean Robot

xiaoxiao2021-02-28  27

题意,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; }

转载请注明原文地址: https://www.6miu.com/read-1450058.html

最新回复(0)