HDU3681 Prison Break（Jan. 28th, 2019） 状压DP BFS

枚举每一个点{
    记忆化数组赋为inf；
    入队；
    广搜{
        取出队头；弹出队头；
        如果答案较记忆化数组不优，跳过；
        枚举扩展点{
            若不在区域内，跳过；
            若不可通过（“D”），跳过；
            入队；
        }
    }
    枚举每一个点{
        记录距离；
    }
}

dp[0][0]=检验值;
枚举状态{
    枚举前一点{
        如果状态不包含前一点，跳过；
        如果前置状态未计算，跳过；
        如果当前状态包含所有开关及起点，就返回1；
        枚举当前点{
            如果状态包括当前点，跳过；
            如果当前点与前一点不连通，跳过；
            如果当前点是电池，就充满电；
            TSP经典转移方程；
        }
    }
    如果状态包含了所有开关，就统计最大电量；
}
返回0；

// La Pluie
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct point{int x, y, r;} p[16];
struct node{int x, y, d;};
char c[20];
int dis[16][16], dp[65536][16], t, mem[16][16], n, m, map[16][16], tgs, start;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, inf = 0x3f3f3f3f;
bool ctrl(int x, int y){return x <= n && x >= 1 && y <= m && y >= 1;}
void bfs(node s){
    queue <node> q; q. push(s);
    while(!q. empty()){
        node u = q. front(); q. pop();
        int x = u. x, y = u. y, d = u. d;
        if(mem[x][y] < d) continue; mem[x][y] = d;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(!ctrl(nx, ny)) continue;
            if(map[nx][ny]) continue;
            q. push((node){nx, ny, d + 1});
        }
    }
}
bool author(int d){
    dp[1 << start - 1][start] = d;
    for(int i = 0; i < (1 << t); i++){
        for(int j = 1; j <= t; j++){ // previous
            if(!(i & (1 << j - 1))) continue;
            if(dp[i][j] == -1) continue;
            if((i & tgs) == tgs) return 1;
            for(int k = 1; k <= t; k++){ // present
                if(i & (1 << k - 1)) continue;
                if(dis[j][k] == inf) continue;
                if(dp[i][j] < dis[j][k]) continue;
                dp[i | (1 << k - 1)][k] = max(dp[i | (1 << k - 1)][k], dp[i][j] - dis[j][k]);
                if(p[k]. r == 2) dp[i | (1 << k - 1)][k] = d;
            }
        }
    }
    return 0;
}
int main(){
    while(~scanf("%d %d", &n, &m) && (n || m)){
        memset(map, 0, sizeof(map)); tgs = 0, t = 0;
        for(int i = 1; i <= n; i++){
            scanf("%s", c + 1);
            for(int j = 1; j <= m; j++){
                if(c[j] == 'F') p[++t] = (point){i, j, 1}, tgs |= 1 << t - 1, start = t;
                if(c[j] == 'G') p[++t] = (point) {i, j, 2};
                if(c[j] == 'Y') p[++t] = (point) {i, j, 3}, tgs |= 1 << t - 1;
                if(c[j] == 'D') map[i][j] = 1;
            }
        }
        memset(dis, 0x3f, sizeof(dis));
        for(int i = 1; i <= t; i++){
            memset(mem, 0x3f, sizeof(mem));
            bfs((node){p[i]. x, p[i]. y, 0});
            for(int j = 1; j <= t; j ++){
                dis[i][j] = dis[j][i] = mem[p[j]. x][p[j]. y];
            }
        }
//      for(int i = 0; i <= t; i++){printf("p[%d] = (%d, %d, %d)\n", i, p[i]. x, p[i]. y, p[i]. r);}
//      for(int i = 0; i <= t; i++){for(int j = 0; j <= t; j ++){printf("%d ", dis[i][j]);}printf("\n");}
        int l = 0, r = n * m, ans = -1;
        while(l <= r){
            int mid = l + r >> 1;
            memset(dp, -1, sizeof(dp));
//          printf("mid = %d\n", mid);
            if(author(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}