Problem Description
Rompire is a robot kingdom and a lot of robots live there peacefully. But one day, the king of Rompire was captured by human beings. His thinking circuit was changed by human and thus became a tyrant. All those who are against him were put into jail, including our clever Micheal#1. Now it’s time to escape, but Micheal#1 needs an optimal plan and he contacts you, one of his human friends, for help. The jail area is a rectangle contains n×m little grids, each grid might be one of the following: 1) Empty area, represented by a capital letter ‘S’. 2) The starting position of Micheal#1, represented by a capital letter ‘F’. 3) Energy pool, represented by a capital letter ‘G’. When entering an energy pool, Micheal#1 can use it to charge his battery ONLY ONCE. After the charging, Micheal#1’s battery will become FULL and the energy pool will become an empty area. Of course, passing an energy pool without using it is allowed. 4) Laser sensor, represented by a capital letter ‘D’. Since it is extremely sensitive, Micheal#1 cannot step into a grid with a laser sensor. 5) Power switch, represented by a capital letter ‘Y’. Once Micheal#1 steps into a grid with a Power switch, he will certainly turn it off. In order to escape from the jail, Micheal#1 need to turn off all the power switches to stop the electric web on the roof—then he can just fly away. Moving to an adjacent grid (directly up, down, left or right) will cost 1 unit of energy and only moving operation costs energy. Of course, Micheal#1 cannot move when his battery contains no energy. The larger the battery is, the more energy it can save. But larger battery means more weight and higher probability of being found by the weight sensor. So Micheal#1 needs to make his battery as small as possible, and still large enough to hold all energy he need. Assuming that the size of the battery equals to maximum units of energy that can be saved in the battery, and Micheal#1 is fully charged at the beginning, Please tell him the minimum size of the battery needed for his Prison break.
Input
Input contains multiple test cases, ended by 0 0. For each test case, the first line contains two integer numbers n and m showing the size of the jail. Next n lines consist of m capital letters each, which stands for the description of the jail.You can assume that 1<=n,m<=15, and the sum of energy pools and power switches is less than 15.
Output
For each test case, output one integer in a line, representing the minimum size of the battery Micheal#1 needs. If Micheal#1 can’t escape, output -1.
Sample Input
5 5 GDDSS SSSFS SYGYS SGSYS SSYSS 0 0
Sample Output
4
Source
状态压缩dp+bfs
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 15 using namespace std; 16 int dirx[]={0,0,-1,1}; 17 int diry[]={-1,1,0,0}; 18 #define PI acos(-1.0) 19 #define max(a,b) (a) > (b) ? (a) : (b) 20 #define min(a,b) (a) < (b) ? (a) : (b) 21 #define ll long long 22 #define eps 1e-10 23 #define MOD 1000000007 24 #define N 17 25 #define inf 1e12 26 int n,m; 27 char mp[N][N]; 28 int states; 29 int final_state;//要达到的目标状态 30 int start; 31 int dis[N][N][N][N]; 32 int dp[1<<N][N]; 33 34 struct Node{ 35 int x,y; 36 }node[N*N]; 37 void bfs(int st){//每一点和其他点的最短距离 38 int x=node[st].x; 39 int y=node[st].y; 40 queue<Node>q; 41 q.push(node[st]); 42 dis[x][y][x][y]=0; 43 Node t1,t2; 44 while(!q.empty()){ 45 t1=q.front(); 46 q.pop(); 47 for(int i=0;i<4;i++){ 48 //t2=t1; 49 t2.x=t1.x+dirx[i]; 50 t2.y=t1.y+diry[i]; 51 if(t2.x<0 || t2.x>=n || t2.y<0 || t2.y>=m) continue; 52 if(mp[t2.x][t2.y]=='D') continue; 53 if(dis[x][y][t2.x][t2.y]!=-1) continue; 54 dis[x][y][t2.x][t2.y]=dis[x][y][t1.x][t1.y]+1; 55 q.push(t2); 56 } 57 } 58 } 59 bool DP(int limit){ 60 memset(dp,-1,sizeof(dp)); 61 dp[(1<<start)][start]=limit; 62 int res=-1; 63 for(int i=0;i<(1<<states);i++){ 64 for(int j=0;j<states;j++){ 65 if((i&(1<<j))==0)continue; 66 if(dp[i][j]==-1) continue; 67 if((i&(final_state))==final_state){ 68 res=max(res,dp[i][j]); 69 } 70 71 for(int k=0;k<states;k++){ 72 if((i&(1<<k))!=0) continue; 73 if(dis[node[j].x][node[j].y][node[k].x][node[k].y]==-1) continue; 74 if(j==k) continue; 75 if(dp[i][j]<dis[node[j].x][node[j].y][node[k].x][node[k].y]) continue; 76 dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]-dis[node[j].x][node[j].y][node[k].x][node[k].y]); 77 if(mp[node[k].x][node[k].y]=='G') dp[i|(1<<k)][k]=limit; 78 } 79 80 } 81 } 82 return res>=0; 83 84 } 85 int main() 86 { 87 while(scanf("%d%d",&n,&m)==2){ 88 if(n==0 && m==0){ 89 break; 90 } 91 states=0; 92 final_state=0; 93 for(int i=0;i<n;i++){ 94 scanf("%s",mp[i]); 95 for(int j=0;j<m;j++){ 96 if(mp[i][j]=='F'){ 97 node[states].x=i; 98 node[states].y=j; 99 start=states; 100 final_state+=(1<<states); 101 states++; 102 } 103 else if(mp[i][j]=='Y'){ 104 node[states].x=i; 105 node[states].y=j; 106 final_state+=(1<<states); 107 states++; 108 } 109 else if(mp[i][j]=='G'){ 110 node[states].x=i; 111 node[states].y=j; 112 states++; 113 } 114 } 115 } 116 117 memset(dis,-1,sizeof(dis)); 118 for(int i=0;i<states;i++){ 119 bfs(i); 120 }//两两之间的最短距离已求出,保存于dis 121 122 int low=0; 123 int high=300; 124 int ans=-1; 125 while(low<=high){ 126 int mid=(low+high)>>1; 127 if(DP(mid)){ 128 ans=mid; 129 high=mid-1; 130 } 131 else{ 132 low=mid+1; 133 } 134 } 135 printf("%d ",ans); 136 137 } 138 return 0; 139 }
TLE代码，想不通
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 15 using namespace std; 16 int dirx[]={0,0,-1,1}; 17 int diry[]={-1,1,0,0}; 18 #define PI acos(-1.0) 19 #define max(a,b) (a) > (b) ? (a) : (b) 20 #define min(a,b) (a) < (b) ? (a) : (b) 21 #define ll long long 22 #define eps 1e-10 23 #define MOD 1000000007 24 #define N 17 25 #define inf 1e12 26 int n,m; 27 char mp[N][N]; 28 int states; 29 int final_state;//要达到的目标状态 30 int start; 31 int dis[N][N][N][N]; 32 int dp[1<<N][N]; 33 int vis[N]; 34 35 struct Node{ 36 int x,y; 37 }node[N*N]; 38 void bfs(int st){//每一点和其他点的最短距离 39 int x=node[st].x; 40 int y=node[st].y; 41 queue<Node>q; 42 q.push(node[st]); 43 dis[x][y][x][y]=0; 44 Node t1,t2; 45 while(!q.empty()){ 46 t1=q.front(); 47 q.pop(); 48 for(int i=0;i<4;i++){ 49 //t2=t1; 50 t2.x=t1.x+dirx[i]; 51 t2.y=t1.y+diry[i]; 52 if(t2.x<0 || t2.x>=n || t2.y<0 || t2.y>=m) continue; 53 if(mp[t2.x][t2.y]=='D') continue; 54 if(dis[x][y][t2.x][t2.y]!=-1) continue; 55 dis[x][y][t2.x][t2.y]=dis[x][y][t1.x][t1.y]+1; 56 q.push(t2); 57 } 58 } 59 } 60 /*bool DP(int limit){ 61 memset(dp,-1,sizeof(dp)); 62 dp[(1<<start)][start]=limit; 63 int res=-1; 64 for(int i=0;i<(1<<states);i++){ 65 for(int j=0;j<states;j++){ 66 if((i&(1<<j))==0)continue; 67 if(dp[i][j]==-1) continue; 68 if((i&(final_state))==final_state){ 69 res=max(res,dp[i][j]); 70 } 71 72 for(int k=0;k<states;k++){ 73 if((i&(1<<k))!=0) continue; 74 if(dis[node[j].x][node[j].y][node[k].x][node[k].y]==-1) continue; 75 if(j==k) continue; 76 if(dp[i][j]<dis[node[j].x][node[j].y][node[k].x][node[k].y]) continue; 77 dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]-dis[node[j].x][node[j].y][node[k].x][node[k].y]); 78 if(mp[node[k].x][node[k].y]=='G') dp[i|(1<<k)][k]=limit; 79 } 80 81 } 82 } 83 return res>=0; 84 85 } 86 */ 87 88 bool dfs(int st,int sta,int limit,int mid){ 89 90 //if(limit<0) return false; 91 92 93 if( (sta & final_state) == final_state){ 94 return true; 95 } 96 97 for(int i=0;i<states;i++){ 98 if(dis[node[st].x][node[st].y][node[i].x][node[i].y]==-1) continue; 99 if(vis[i] || limit<dis[node[st].x][node[st].y][node[i].x][node[i].y]) continue; 100 101 if(mp[node[i].x][node[i].y]=='G'){ 102 vis[i]=1; 103 if(dfs(i,sta|(1<<i),mid,mid)){ 104 return true; 105 } 106 vis[i]=0; 107 } 108 else{ 109 vis[i]=1; 110 if(dfs(i,sta|(1<<i),limit-dis[node[st].x][node[st].y][node[i].x][node[i].y],mid)){ 111 return true; 112 } 113 vis[i]=0; 114 } 115 116 } 117 return false; 118 119 } 120 int main() 121 { 122 while(scanf("%d%d",&n,&m)==2){ 123 if(n==0 && m==0){ 124 break; 125 } 126 states=0; 127 final_state=0; 128 for(int i=0;i<n;i++){ 129 scanf("%s",mp[i]); 130 for(int j=0;j<m;j++){ 131 if(mp[i][j]=='F'){ 132 node[states].x=i; 133 node[states].y=j; 134 start=states; 135 final_state+=(1<<states); 136 states++; 137 } 138 else if(mp[i][j]=='Y'){ 139 node[states].x=i; 140 node[states].y=j; 141 final_state+=(1<<states); 142 states++; 143 } 144 else if(mp[i][j]=='G'){ 145 node[states].x=i; 146 node[states].y=j; 147 states++; 148 } 149 } 150 } 151 152 memset(dis,-1,sizeof(dis)); 153 for(int i=0;i<states;i++){ 154 bfs(i); 155 }//两两之间的最短距离已求出,保存于dis 156 157 int low=0; 158 int high=300; 159 int ans=-1; 160 while(low<=high){ 161 int mid=(low+high)>>1; 162 memset(vis,0,sizeof(vis)); 163 vis[start]=1; 164 if(dfs(start,1<<start,mid,mid)){ 165 ans=mid; 166 high=mid-1; 167 } 168 else{ 169 low=mid+1; 170 } 171 } 172 printf("%d ",ans); 173 174 } 175 return 0; 176 }