HDOJ 3681 Prison Break BFS+状态压缩dp+二分

wa了三四天，查错都查到自己没信心了，结果：wa在了一个循环把m写成了n！！！

这种错误你敢信！！！

题意：n*m的地图，其中S是起点，Y是目标点，G是加油站

我们的目标是在S尽可能的少带油（油量定好了就是携带的量的最大值），走一格消耗一点油，每个加油站的油可以让我们补充到携带量的最大值，而且只能补充一次。需要求得最少的携带量，使得我们可以到所有的目标点（所有的Y必须到，所有的G可以去也可以不去）

题目中最重要的一句话：G和Y的数目不超过15！

看到了15和20，这类很小的数据，就知道要用到：状态压缩dp

那么，怎么得到这些状态？

我们需要把起点S，目标点Y，加油站G，这些点从图中拿出来，重新建图，需要求出任意两点之间的距离

因为题目中的地图很小，所以可以对于每一个有用的点，都暴力的搞一次bfs来求图中所有有用的点的距离

最终可以得到一个有用的距离矩阵

在算这个矩阵的过程中，需要有新坐标点和旧坐标点的一一对应，这儿的处理细节比较多

建议多打印中间的过程输出，便于debug

有了这个矩阵，有什么用？

知道起点，知道所有目标点的集合，而且数目很小，我们可以用状态压缩dp！

dp【i】【j】为当前状态量为i，刚刚经过点j时的剩余油量

然后相当于是TSP旅行商问题，判断就好

还有一个很重要的转化：

题中是求的最值：如何把求最值化成判定性问题：二分！

二分答案（所需要携带的油量），当然油量很大的时候，是肯定可以到达的

所以可以找到最小值

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int INF=50000;
const int maxn=16;

char a[maxn][maxn];
bool vis[maxn][maxn];

struct node{
	int x,y,dis;
	char ch;
}mp[maxn*maxn];

int place[maxn*maxn],dp[1<<maxn][maxn],dist[maxn*maxn][maxn*maxn];
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int final,totpoint,startpoint,n,m;

void bfs(node s){
	memset(vis,false,sizeof(vis));
	vis[s.x][s.y]=true;
	queue<node> q;
	while(!q.empty()) q.pop();
	s.dis=0;
	q.push(s);
	while(!q.empty()){
		node u=q.front(),v;
		q.pop();
		for(int k=0;k<4;k++){
			v.x=u.x+dx[k];
			v.y=u.y+dy[k];
			v.dis=u.dis+1;
			if (v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&a[v.x][v.y]!='D'&&!vis[v.x][v.y]){
				v.ch=a[v.x][v.y];
				q.push(v);vis[v.x][v.y]=true;
				if (v.ch!='S'){
					int ss=s.x*m+s.y;
					int vv=v.x*m+v.y;
					dist[place[ss]][place[vv]]=v.dis;
				}
			}
		}
	}
}

void getmap(){
	for(int i=0;i<totpoint;i++)
		for(int j=0;j<totpoint;j++)
			dist[i][j]=INF;
	for(int i=0;i<totpoint;i++) bfs(mp[i]);
}

bool ok(int energy){
	memset(dp,-1,sizeof(dp));
	dp[1<<startpoint][startpoint]=energy;
	for(int i=(1<<startpoint);i<(1<<totpoint);i++)
		for(int j=0;j<totpoint;j++)
			if (dp[i][j]!=-1&&(i&(1<<j))){
				if ((i&final)==final) return true;
				for(int k=0;k<totpoint;k++)
					if (dist[j][k]<=dp[i][j]&&(!(i&(1<<k)))&&k!=j){
						int newpos=i|(1<<k);
						dp[newpos][k]=max(dp[newpos][k],dp[i][j]-dist[j][k]);
						if (mp[k].ch=='G') dp[newpos][k]=energy;
					}
	}
	return false;
}

void debug(){
	for(int i=0;i<totpoint;i++)
		printf("%d %d %d %c\n",i,mp[i].x,mp[i].y,mp[i].ch);
	cout<<endl;
	for(int i=0;i<totpoint;i++)
		for(int j=0;j<totpoint;j++)
			printf("%6d%c",dist[i][j],j==totpoint-1?'\n':' ');
	cout<<endl;
	printf("FINAL:%d\n",final);
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	while(scanf("%d%d",&n,&m),n+m){
		final=totpoint=0;
		memset(place,0,sizeof(place));
		for(int i=0;i<n;i++) scanf("%s",a[i]);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if (a[i][j]!='D'&&a[i][j]!='S'){
					mp[totpoint].x=i;
					mp[totpoint].y=j;
					mp[totpoint].dis=0;
					mp[totpoint].ch=a[i][j];
					place[i*m+j]=totpoint;
					if (a[i][j]=='F') startpoint=totpoint;
					if (a[i][j]=='Y') final=final|(1<<totpoint);
					totpoint++;
				}
		getmap();
		//debug();
		int L=0,R=300,mid,ans=-1;
		while(L<=R){
			mid=(L+R)>>1;
			if (ok(mid)) ans=mid,R=mid-1;
			else L=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;
}