FZU 2186 BFS+狀壓最短路

FZU 2186 BFS+狀壓最短路

一開始看寶藏只有10個，100*100的矩陣，
果斷寫了狀壓BFS，然後果斷超時。。


正解:先不考慮財寶，先做BFS算出，每個財寶之間的最短路（包括起點），然後狀壓最短路處理即可。
注意三中情況：起點為負數，不存在財寶，存在一個財寶且財寶在原點。

#include "stdio.h"
#include "string.h"
#include "algorithm"
#include "queue"
using namespace std;
const int inf=0x3f3f3f3f;

struct Mark
{
    int x,y;
}mark[15];

struct node
{
    int x,y,t;
};
int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
int b[15];
int str[110][110];
int dis[15][15];
int n,m,cnt;
int used[110][110];
int dp[5010][15];

int Min(int a,int b)
{
    if (aq;
    node cur,next;
    int i;

    memset(used,0,sizeof(used));
    cur.x=mark[w].x;
    cur.y=mark[w].y;
    cur.t=0;
    q.push(cur);
    used[mark[w].x][mark[w].y]=1;
    while (!q.empty())
    {
        cur=q.front();
        q.pop();
        for (i=0;i<4;i++)
        {
            next.x=cur.x+dir[i][0];
            next.y=cur.y+dir[i][1];
            if (next.x<0 || next.y<0 || next.x>=n || next.y>=m) continue;
            if (str[next.x][next.y]<0) continue;
            if (used[next.x][next.y]==0)
            {
                used[next.x][next.y]=1;
                next.t=cur.t+1;
                if (str[next.x][next.y]>0)
                {
                    dis[w][str[next.x][next.y]]=Min(dis[w][str[next.x][next.y]],next.t);
                    dis[str[next.x][next.y]][w]=dis[w][str[next.x][next.y]];
                }
                q.push(next);
            }
        }
    }
}

int main()
{
    int i,j,ans,flag,aim,l;
    b[0]=1;
    for (i=1;i<=12;i++)
        b[i]=b[i-1]*2;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        for (i=0;i0 && i+j!=0)
                {
                    mark[++cnt].x=i;
                    mark[cnt].y=j;
                    str[i][j]=cnt;
                }
            }
        if (cnt==0)
        {
            printf("0\n");
            continue;
        }
        if (cnt==1 && str[0][0]>0)
        {
            printf("0\n");
            continue;
        }
        if (str[0][0]<0)
        {
            printf("-1\n");
            continue;
        }
        mark[0].x=0;
        mark[0].y=0;
        memset(dis,inf,sizeof(dis));
        for (i=0;i<=cnt;i++)
            bfs(i);
        flag=1;
        for (i=1;i<=cnt;i++)
            if (dis[0][i]==inf)
            {
                printf("-1\n");
                flag=0;
            }
        if (flag==0) continue;

        memset(dp,inf,sizeof(dp));
        dp[1][0]=0;
        aim=b[cnt+1]-1;
        for (l=0;l<=aim;l++)
            for (i=0;i<=cnt;i++)
                for (j=0;j<=cnt;j++)
                if (i!=j)
                {
                    if ((b[i]&l)==0) continue;
                    if ((b[j]&l)!=0) continue;
                    if (dp[l][i]==inf) continue;
                    dp[l|b[j]][j]=Min(dp[l|b[j]][j],dp[l][i]+dis[i][j]);
                }
        ans=inf;
        for (i=1;i<=cnt;i++)
            ans=Min(ans,dp[aim][i]+dis[i][0]);
        printf("%d\n",ans);

    }
    return 0;
}