hdu 4568 Hunter bfs建圖+TSP狀壓DP

想AC的人請跳過這一段。。。

題目應該都能讀懂。但是個人覺得這題出的很爛，意思太模糊了。

首先，進出次數只能是一次！！這個居然在題目中沒有明確說明，讓我在當時看到題目的時候無從下手。

因為我想到了這幾個數據：

1 1 1                   1 9 1                  -1 -1 -1

-1-1-1                     9 9 9                  -1 1 -1

1 1 1                       1 9 1                  -1 -1 -1

6個寶藏                  四個角是寶藏      中間是寶藏

第一個數據如果進出2次，就可以拿走全部的6個寶藏，也符合題目的“bring out all treasures he can take”。

即使是規定了進出只能一次，那這個數據又該輸出什麼？（ if nothing James can get, please output 0）

第二個數據如果進出4次，就可以最快的拿走全部寶藏。

第三個數據唯一的寶藏拿不走。

不過，這題的測試數據中並沒有上面的例子。

以上為個人YY

以下為題解：

進出一次，找到所有能找到的寶藏，裸的TSP問題。

首先選一個自己喜歡的算法建圖。將整個邊界理解成一個點，找到每兩個寶藏之間的最短距離和每個寶藏的離邊界點的最短距離。

然後就是TSP，狀態壓縮DP解。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n,m,tre;
int ID[205][205];
int map[205][205];
int dis[20][20];
bool vis[205][205];
int dp[1<<16][20];
struct node
{
    int x,y;
}t[20];
struct node2
{
    int x,y,dis;
    bool operator <(const node2 & f) const
    {
        return dis>f.dis;
    }
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool isok(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=-1;
}
void bfs(int k)
{
    priority_queue<node2> Q;
    int v[20]={0};
    memset(vis,0,sizeof(vis));
    node2 f,r;
    r.x=t[k].x;
    r.y=t[k].y;
    r.dis=0;
    Q.push(r);
    v[k]=1;
    vis[r.x][r.y]=1;
    int tot=1,id;
    while(!Q.empty())
    {
        f=Q.top(); Q.pop();
        if(!v[0]&&(f.x==0||f.y==0||f.x==n-1||f.y==m-1))
        {
            v[0]=1;
            dis[k][0]=f.dis;
            dis[0][k]=f.dis+map[t[k].x][t[k].y];
            tot++;
            if(tot==tre+1) return;
        }
        id=ID[f.x][f.y];
        if(id&&!v[id])
        {
            tot++;
            v[id]=1;
            dis[k][id]=f.dis;
            if(tot==tre+1) return;
        }
        for(int d=0;d<4;d++)
        {
            r.x=f.x+dx[d];
            r.y=f.y+dy[d];
            r.dis=f.dis+map[r.x][r.y];
            if(isok(r.x,r.y)&&!vis[r.x][r.y])
            {
                vis[r.x][r.y]=1;
                Q.push(r);
            }
        }
    }
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(ID,0,sizeof(ID));
        memset(dis,0x3f,sizeof(dis));
        memset(dp,0x3f,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&map[i][j]);
        scanf("%d",&tre);
        for(int i=1;i<=tre;i++)
        {
            scanf("%d%d",&t[i].x,&t[i].y);
            ID[t[i].x][t[i].y]=i;
        }
        for(int i=1;i<=tre;i++)
            {
                bfs(i);
            }
        dis[0][0]=0;
        if(!tre) {printf("0");continue;}

        for(int i=0;i<=tre;i++)
        {
            dp[1<<i][i]=dis[0][i];
        }
        int end=(1<<(tre+1));
        for(int i=0;i<end;i++)
        {
            for(int j=0;j<=tre;j++)
            {
                if((i>>j)&1)
                {
                    for(int k=0;k<=tre;k++)
                    {
                        if((i>>k)&1)
                        {
                            dp[i][j]=min(dp[i][j],dp[i&(~(1<<j))][k]+dis[k][j]);
                        }
                    }
                }
            }
        }
        printf("%d\n",dp[end-1][0]);
    }
    return 0;
}