hdu 3681 Prison Break

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3681
제목: n*m 행렬에는 15개를 넘지 않는 G와 Y가 있습니다. 모든 Y를 통과해야 합니다. 한 번 이동하려면 전기가 필요합니다. 최소한 몇 개의 배터리가 필요하냐고 물어보세요.
사고방식: 만약에 G가 없다면 아주 간단한 최단길이다. G가 있으면 매우 복잡하다. 우리는 2분에 V를 토론하고 상압 dp로 보조를 한다. dp[S][k]=max(dp[S+{j}][j]-dis[j][k]) 또는 dp[S/{k}]=max([Sdp][j]-dis[j][k])dp][k][k]는 집합을 대표할 때 j에 도달할 때의 남은 전력량을 구조체로 먼저 모든 Y와 G를 저장하면 그들에게 가장 짧은 집합을 형성할 수 있다.
 

#include
#include
#include
#include
#include
#define maxn 17
#define  inf 100000

using namespace std;

int n, m, sx, sy, cnt, goal, start;
char Map[maxn][maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn][maxn];
int dp[1 << maxn][maxn];
int x[] = {1, 0, -1, 0};
int y[] = {0, 1, 0, -1};

struct P
{
    int x;
    int y;
} node[maxn];

void bfs(int num)
{
    int xx = node[num].x;
    int yy = node[num].y;
    if(Map[xx][yy] == 'D')
        return ;

    for(int i = 0; i < n; i++)
    {
        for(int j =0; j < m; j++)
            dis[num][i][j] = -1;
    }

    queue
 Q;
    Q.push(node[num]);
    dis[num][xx][yy] = 0;
    P tmp, cur;
    while(!Q.empty())
    {
        tmp = Q.front();
        Q.pop();

        for(int i = 0; i < 4; i++)
        {
            cur.x = tmp.x + x[i];
            cur.y = tmp.y + y[i];
            if(cur.x < 0 || cur.y < 0 || cur.x >= n || cur.y >= m ||
                    Map[cur.x][cur.y] == 'D' || dis[num][cur.x][cur.y] != -1)
                continue;

            dis[num][cur.x][cur.y] = dis[num][tmp.x][tmp.y] + 1;
            Q.push(cur);
        }
    }
}

bool check(int v)
{
    memset(dp, -1, sizeof(dp));
    dp[1 << start][start] = v;

    for(int i = 0; i < (1 << cnt); i++)
    {
        for(int j = 0; j < cnt; j++)
        {
            if(dp[i][j] == -1 || i & (1 << j) == 0)
                continue;
            if((i & goal) == goal)
                return true;

            for(int k = 0; k < cnt; k++)
            {
                if(i == j || (i & (1 << k)) != 0)
                    continue;
                int tmp = dis[j][node[k].x][node[k].y];
                if(dp[i][j] < tmp || tmp == -1)
                    continue;
                dp[i | (1 << k)][k] = max(dp[i | (1 << k)][k], dp[i][j] - tmp);
                if(Map[node[k].x][node[k].y] == 'G') dp[i | (1 << k)][k] = v;
            }
        }
    }
    return false;
}

int main()
{
    while(~scanf("%d %d", &n, &m), n + m)
    {
        goal = 0;
        cnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", Map[i]);
            for(int j = 0; Map[i][j]; j++)
            {
                if(Map[i][j]=='F')
                {
                    start=cnt;
                    goal|=(1<