Description
Consider the room floor paved with square tiles whose size fits the cleaning robot (1 * 1). There are 'clean tiles' and 'dirty tiles', and the robot can change a 'dirty tile' to a 'clean tile' by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.
Your task is to write a program which computes the minimum number of moves for the robot to change all 'dirty tiles' to 'clean tiles', if ever possible.
bfs建图加状压DP（据说bfs+dfs也能过）。表示好像做麻烦了，bfs时先用了链式前项星存，后转到了矩阵。然后开始状压，因为dp[][]第一维开了30还RE了一次。写了两个小时，还是蛮有成就感的。。。（各种小调试太闹人QAQ）各种调试的小毛病都写在代码里了233
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,flag,cnt;
char ch,map[30][30];
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int head[20],to[400],nxt[400],dis[400],tot;
int fnd[20][20],ans,dp[5010][30];
struct node
{
int x,y,sum;//sum用来bfs时记录经过的步数
}a[20];//脏物品的坐标和bfs用的结构写到了一起
queue <node> q;
bool v[30][30];//防止bfs搜回去
void add(int x,int y,int z)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
dis[tot]=z;
}
void bfs(int x,int y,int st)
{
memset(v,0,sizeof(v));
node tmp;
tmp.x=x,tmp.y=y,tmp.sum=0;
v[x][y]=1;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=tmp.x+dx[i],yy=tmp.y+dy[i];
if(xx<0||xx>n||yy<0||yy>m||map[xx][yy]=='x'||v[xx][yy]) continue;//不能只搜图的下半部分，有可能需要从上边绕到下部
if(map[xx][yy]=='*'||map[xx][yy]=='o'||map[xx][yy]=='.')
{
node temp;
temp.x=xx, temp.y=yy,temp.sum=tmp.sum+1;
v[xx][yy]=1;
q.push(temp);
if(map[xx][yy]!='.'&&(xx>a[st].x||(xx==a[st].x&&yy>a[st].y)))//只加后边的确保只加边一次，好判断是否无解
for(int i=0;i<=cnt;i++)
{
if(a[i].x==xx&&a[i].y==yy)
add(i,st,temp.sum),add(st,i,temp.sum);//一定是temp.sum，因为修后一步也要迈
}
}
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)&&n!=0&&m!=0)
{
memset(head,-1,sizeof(head));
cnt=0; tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
ch=getchar();
while(ch!='.'&&ch!='x'&&ch!='*'&&ch!='o')
ch=getchar();
map[i][j]=ch;
if(ch=='*'||ch=='o') a[cnt].x=i,a[cnt++].y=j;//cnt从0开始好dp
if(ch=='o') flag=cnt-1;
}
cnt--;
for(int i=0;i<=cnt;i++)
bfs(a[i].x,a[i].y,i);
if(flag!=0)
{
swap(a[flag],a[0]);
swap(head[0],head[flag]);//链式前项星0和出发点对调，更换头指针
}
for(int i=0;i<=cnt;i++)//出边的另一端点也要换
{
for(int j=head[i];j!=-1;j=nxt[j])
if(to[j]==0) to[j]=flag;
else if(to[j]==flag) to[j]=0;
}
flag=0;//重复利用flag判断无解
for(int i=0;i<=cnt;i++)
{
//printf("%d %d %d :",a[i].x,a[i].y,i);
for(int j=head[i];j!=-1;j=nxt[j])
{
//printf("%d %d ;",to[j],dis[j]);
flag++;
fnd[i][to[j]]=dis[j];
}
//puts("");
if(flag!=cnt)//一定是cnt，不是cnt-1
{
flag=-1;break;
}
else flag=0;
}
if(flag==-1)
{
printf("-1\n");
continue;
}
/*for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
printf("%d ",fnd[i][j]);
puts("");
}*/
for(int s=0;s<(1<<cnt);s++)//最后一个搜到的一定是1<<个数-1
for(int i=1;i<=cnt;i++)
if(s&(1<<i-1))
{
if(s==(1<<i-1))
dp[s][i]=fnd[0][i];
else
{
dp[s][i]=INF;//初始化
for(int j=1;j<=cnt;j++)
{
if(s&(1<<j-1)&&j!=i)
dp[s][i]=min(dp[s][i],dp[s^(1<<i-1)][j]+fnd[j][i]);//不能写s-(1<<i-1),时间慢
}
}
}
/*for(int i=0;i<=(1<<cnt)-1;i++)
{
for(int j=1;j<=cnt;j++)
printf("%d ",dp[i][j]);
puts("");
}*/
ans=1<<30;
for(int i=1;i<=cnt;i++)
ans=min(ans,dp[(1<<cnt)-1][i]);
printf("%d\n",ans);
}
return 0;
}代码好麻烦，不过过了就好23333