首页技术正文

POJ 2688 Cleaning Robot

程序员海宇技术 2022年11月6日

0 收藏 852 点赞 725 浏览 1312 个字

题意：

给你一个n*m的图。你从’o’点出发，只能走路（图中的’.’）不能穿墙（图中的’x’），去捡垃圾（图中的’ * ‘）问最少走多少步能捡完所有垃圾，如有垃圾捡不了，输出-1.

思路：

有两个思路

我会的
我不会的
（嗯学一下小杰）

我会的—->BFS+全排列（next_permutation可水之）

我不会的–>BFS+状压DP

//By: Sirius_Ren
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int p[11][2],tot,sx,sy,xx[]={1,-1,0,0},yy[]={0,0,1,-1},b[25][25],n,m,vis[25][25],f[25],minn;
char a[25][25];
queue<pair<int,int> > q;
int main()
{
    st:while(scanf("%d%d",&m,&n)&&(m||n)){
        for(int i=1;i<=11;i++)f[i]=i;minn=0x3fffffff,tot=0;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++){
                scanf("%c",&a[i][j]);
                if(a[i][j]=='*')p[++tot][0]=i,p[tot][1]=j;
                else if(a[i][j]=='o')sx=i,sy=j;
            }
        p[++tot][0]=sx,p[tot][1]=sy;
        for(int ii=1;ii<=tot;ii++){
            memset(vis,-1,sizeof(vis));
            q.push(make_pair(p[ii][0],p[ii][1]));
            vis[p[ii][0]][p[ii][1]]=0;
            while(!q.empty()){
                pair<int,int> Q=q.front();q.pop();
                for(int i=0;i<=3;i++){
                    char tx=Q.first+xx[i],ty=Q.second+yy[i];
                    if((a[tx][ty]=='.'||a[tx][ty]=='*'||a[tx][ty]=='o')&&!(~vis[tx][ty]))
                        vis[tx][ty]=vis[Q.first][Q.second]+1,q.push(make_pair(tx,ty));
                }
            }
            for(int i=1;i<=tot;i++)
            if(~vis[p[i][0]][p[i][1]])b[ii][i]=vis[p[i][0]][p[i][1]];
            else {printf("-1\n");goto st;}
        }
        do{
            int sum=0;
            for(int i=2;i<=tot;i++) sum+=b[f[i-1]][f[i]];
            minn=min(minn,sum);
        }while(next_permutation(f+1,f+tot));
        printf("%d\n",minn);
    }
}