hdu 3681 Prison Break (旅行商问题)

Prison BreakTime Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2436 Accepted Submission(s): 612

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>//#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 20#define maxx 32770#define mod 1000000000#define INF 0x3f3f3f3fusing namespace std;int n,m,ans,cnt,ma;int sx,sy,est;int dp[maxx][17];int id[maxn][maxn],dist[maxn][maxn];bool vis[maxn][maxn],vv[maxn];char mp[maxn][maxn];char s[maxn];int dx[]={-1,1,0,0};int dy[]={0,0,-1,1};struct node{ int x,y,step;}cur,now;queue<node>q;void bfs(int bx,int by,int k){ int i,j,nx,ny,tx,ty; memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); cur.x=bx; cur.y=by; cur.step=0; vis[bx][by]=1; q.push(cur); while(!q.empty()) { now=q.front(); q.pop(); nx=now.x; ny=now.y; if(mp[nx][ny]=='G'||mp[nx][ny]=='Y'||mp[nx][ny]=='F') dist[k][id[nx][ny]]=now.step; for(i=0;i<4;i++) { tx=nx+dx[i]; ty=ny+dy[i]; if(tx<1||tx>n||ty<1||ty>m||mp[tx][ty]=='D'||vis[tx][ty]) continue ; cur.x=tx; cur.y=ty; cur.step=now.step+1; vis[tx][ty]=1; q.push(cur); } }}void presolve(){ int i,j,t; est=0; cnt=t=-1; memset(dist,0x3f,sizeof(dist)); memset(vv,0,sizeof(vv)); for(i=1;i<=n;i++) // 编号 bfs预处理 { for(j=1;j<=m;j++) { if(mp[i][j]=='G'||mp[i][j]=='Y') { id[i][j]=++cnt; if(mp[i][j]=='Y') { est|=(1<<cnt); vv[cnt]=1; } } } } cnt++; vv[cnt]=1; id[sx][sy]=cnt; bfs(sx,sy,cnt); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(mp[i][j]=='G'||mp[i][j]=='Y') bfs(i,j,++t); } } ma=1<<cnt;}bool isok(int power){ int i,j,k,st; dp[0][cnt]=power; for(i=0;i<ma;i++) { for(j=0;j<=cnt;j++) { if(dp[i][j]==-1) continue ; if((i&est)==est) return true ; for(k=0;k<=cnt;k++) { if(k==j||(i&(1<<k))||dist[k][j]>dp[i][j]) continue ; st=i|(1<<k); if(vv[k]) dp[st][k]=max(dp[st][k],dp[i][j]-dist[k][j]); else dp[st][k]=power; } } } return false ;}void solve(){ int i,j,le,ri,mid; le=0; ri=1000; while(le<ri) { mid=(le+ri)>>1; memset(dp,-1,sizeof(dp)); if(isok(mid)) ri=mid; else le=mid+1; } if(le==1000) ans=-1; else ans=le;}int main(){ int i,j; while(scanf("%d%d",&n,&m),n||m) { for(i=1;i<=n;i++) { scanf("%s",s); for(j=1;j<=m;j++) { mp[i][j]=s[j-1]; if(mp[i][j]=='F') sx=i,sy=j; } } presolve(); solve(); printf("%d\n",ans); } return 0;}