hdu3681_状压dp+bfs+二分答案

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3681

题意：n*m的矩阵，一个人带着一块满电池从 'F' 出发，走遍所有的 'Y'(开关) ,可以从四个方向（上下左右），每走一步消耗一格电，'S'是空地(可走)，'G'是加油站(把电池加满后变为空地)，'D'是不能走的禁地。问关掉所有的开关最少最少带的电池是多少格的？如果不存在输出 '-1'

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 #define INF 0x3f3f3f3f
  7 using namespace std;
  8 
  9 const int N = 16, M = 1 << N;
 10 int dp[M][N], k, n, m, first, k2;
 11 int dis[N][N], dist[N][N];//dis[x][y]为某个特殊点到(x, y)的距离, dist[i][j]为(num[i].x, num[i].y)到(num[j].x, num[j].y)的距离
 12 char a[20][20];
 13 struct node {
 14     int x, y;
 15 }num[20];
 16 int to[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 17 void bfs(int x, int y)
 18 {
 19     queue <int> q1, q2;
 20     q1.push(x), q2.push(y);
 21     for(int i = 0; i < n; i++)
 22         for(int j = 0; j < m; j++)
 23             dis[i][j] = INF;
 24     dis[x][y] = 0;
 25     while(q1.size())
 26     {
 27         int x1 = q1.front(), y1 = q2.front();
 28         q1.pop();
 29         q2.pop();
 30         for(int i = 0; i < 4; i++)
 31         {
 32             int x2 = x1 + to[i][0], y2 = y1 + to[i][1];
 33             if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || a[x2][y2] == 'D')
 34                 continue;
 35             if(dis[x2][y2] > dis[x1][y1] + 1)
 36             {
 37                 dis[x2][y2] = dis[x1][y1] + 1;
 38                 q1.push(x2), q2.push(y2);
 39             }
 40         }
 41     }
 42 }
 43 void init()
 44 {    
 45     for(int i = 0; i < k2; i++)
 46     {
 47         bfs(num[i].x, num[i].y);//bfs点(num[i].x, num[i].y)到各个点之间的距离
 48         for(int j = 0; j < k2; j++)
 49         {
 50             if(i != j){
 51                 dist[i][j] = dis[num[j].x][num[j].y];
 52                 //cout << i << " " << j <<  " "<< dist[i][j] << endl;
 53             }
 54         }
 55     }
 56 }
 57 bool rec(int p)
 58 {
 59     int res = (1 << k) - 1;
 60     for(int i = 0; i < (1 << k2); i++)
 61         for(int j = 0; j < k2; j++)
 62             dp[i][j] = -1 * INF;
 63     dp[1 << first][first] = p;
 64     for(int i = (1 << first); i < (1 << k2); i++)
 65     {
 66         for(int j = 0; j < k2; j++)
 67         {
 68             if(dp[i][j] < 0 || !(i & (1 << j)))
 69                 continue;
 70             if((i & res) == res)
 71                 return true;
 72             for(int l1 = 0; l1 < k2; l1++)
 73             {
 74                 if(i & (1 << l1))
 75                     continue;
 76                 int next = i | (1 << l1);
 77                 dp[next][l1] = max(dp[next][l1], dp[i][j] - dist[j][l1]);
 78                 if(dp[next][l1] >= 0 && l1 >= k)
 79                     dp[next][l1] = p;
 80             }
 81         }
 82     }
 83     return false;
 84 }
 85 int main()
 86 {
 87     while(~scanf("%d %d", &n, &m) && (n + m))
 88     {
 89         k = 0;        
 90         for(int i = 0; i < n; i++){
 91             getchar();
 92             for(int j = 0; j < m; j++)
 93             {
 94                 scanf("%c", &a[i][j]);
 95                 if(a[i][j] == 'F' || a[i][j] == 'Y')
 96                 {                    
 97                     num[k].x = i, num[k].y = j;
 98                     k++;
 99                 }
100                 if(a[i][j] == 'F')
101                     first = k - 1;
102             }
103         }
104         k2 = k;   
105         for(int i = 0; i < n; i++){
106             for(int j = 0; j < m; j++)
107             {
108                 if(a[i][j] == 'G')
109                 {                    
110                     num[k2].x = i, num[k2].y = j;
111                     k2++;
112                 }
113             }
114         }          
115         init(); 
116         int l = 0, r = 300, flag = 0;
117         while(l <= r)
118         {
119             int mid = (l + r) / 2;
120             if(rec(mid))
121             {
122                 flag = 1;
123                 r = mid - 1;
124             }
125             else
126                 l = mid + 1;
127             //cout << l << " " << r << endl;
128         }        
129         if(!flag)
130             printf("-1
");
131         else
132             printf("%d
", l);        
133     }
134     return 0;
135 }