二分答案+状压DFS+BFS预处理
答案是通过二分得到的，每次得到的mid进行验证，验证可以状压DP也可以DFS
DFS||DP的时候，如果一格一格走，会TLE。事实上我们只关心Y、G、F这几个格子的状态，对于S不知道情况对得到答案毫无影响，所以采用BFS预处理，求出Y、G、F这几个格子两两之间的最短路程。
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <stack> #include <map> #include <vector> using namespace std; const int maxn=20; int n,m; char s[maxn][maxn]; int flag[maxn][maxn]; int dp[maxn][(1<<15)+10]; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int dis[maxn][maxn]; int Min[maxn][maxn]; int sx,sy; bool now_ans; int all_state; int id,num_Y,num_G; struct cha { int a,b; }cha[maxn]; struct Node{ int a,b; int tot; Node(int v1,int v2,int v3) {a=v1,b=v2;tot=v3;} }; void read() { for(int i=0; i<n; i++) scanf("%s",s[i]); } bool f(int a,int b) { if(a>=0&&a<n&&b>=0&&b<m) return 1; return 0; } void bfs(int a,int b) { queue<Node>Q; for(int i=0;i<n;i++) for(int j=0;j<m;j++) Min[i][j]=0x7fffffff; Min[a][b]=0; Node node(a,b,0); Q.push(node); while(!Q.empty()) { Node head=Q.front(); Q.pop(); if(flag[head.a][head.b]!=-1) { dis[flag[a][b]][flag[head.a][head.b]]=head.tot; dis[flag[head.a][head.b]][flag[a][b]]=head.tot; } for(int i=0;i<4;i++) { int newx=head.a+dir[i][0]; int newy=head.b+dir[i][1]; if(!f(newx,newy)) continue; if(s[newx][newy]=='D') continue; if(head.tot+1<Min[newx][newy]) { Min[newx][newy]=head.tot+1; Node node(newx,newy,head.tot+1); Q.push(node); } } } } void init() { for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(s[i][j]=='F') sx=i,sy=j; memset(flag,-1,sizeof flag); num_Y=0,num_G=0; for(int i=0; i<n; i++) for(int j=0; j<m; j++){ if(s[i][j]=='G') num_G++; else if(s[i][j]=='Y') num_Y++; } id=0; for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(s[i][j]=='Y') { cha[id].a=i,cha[id].b=j; flag[i][j]=id++; } for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(s[i][j]=='G') { cha[id].a=i,cha[id].b=j; flag[i][j]=id++; } cha[id].a=sx,cha[id].b=sy; flag[sx][sy]=id++; all_state=(1<<num_Y)-1; for(int i=0;i<id;i++) for(int j=0;j<id;j++) dis[i][j]=0x7fffffff; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(flag[i][j]!=-1) bfs(i,j); } void dfs(int now_id,int state,int now,int MAX) { if((state&all_state)==all_state) { now_ans=1; return; } if(now==0) return; for(int i=0;i<id;i++) { int new_state; if(i==now_id) continue; if(dis[now_id][i]==0x7fffffff) continue; int newx=cha[i].a; int newy=cha[i].b; if(s[newx][newy]=='G') { //不使用 new_state=state; if(now-dis[i][now_id]>dp[i][new_state]) { dp[i][new_state]=now-dis[i][now_id]; dfs(i,new_state,now-dis[i][now_id],MAX); if(now_ans) return; } //使用 new_state=(state|(1<<i)); if(now-dis[i][now_id]>=0&&MAX>dp[i][new_state]) { s[newx][newy]='S'; dp[i][new_state]=MAX; dfs(i,new_state,MAX,MAX); s[newx][newy]='G'; if(now_ans) return; } } else if(s[newx][newy]=='Y') { new_state=(state|(1<<i)); if(now-dis[i][now_id]>dp[i][new_state]) { s[newx][newy]='S'; dp[i][new_state]=now-dis[i][now_id]; dfs(i,new_state,now-dis[i][now_id],MAX); s[newx][newy]='Y'; if(now_ans) return; } } else { new_state=state; if(now-dis[i][now_id]>dp[i][new_state]) { dp[i][new_state]=now-dis[i][now_id]; dfs(i,new_state,now-dis[i][now_id],MAX); if(now_ans) return; } } } } bool judge(int lim) { now_ans=0; memset(dp,-1,sizeof dp); dp[id-1][0]=lim; dfs(id-1,0,lim,lim); return now_ans; } void work() { int ans=-1; int l=0,r=300; while(l<=r) { int mid=(l+r)/2; if(judge(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d ",ans); } int main() { while(~scanf("%d%d",&n,&m)) { if(!n&&!m) break; read(); init(); work(); } return 0; }