POJ 2688 BFS+狀壓DP

POJ 2688 BFS+狀壓DP

標准的TSP問題

m*n矩陣，有不超過10個需要走到的點，給出起點，問走最少的步子把所有點走完

BFS出每個必須走到的點的最短距離

然後狀壓DP即可

#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;

const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
int inf=0x7fffffff;
int aim,cnt,n,m,s_x,s_y;
int b[20];
int used[25][25];
int dp[5010][25];
char str[25][25];
int dis[25][25];
struct node
{
    int x,y,step;
};

struct Point
{
    int x,y;
}point[25];

int Min(int a,int b)
{
    if (aq;
    node cur,next;
    int i;
    cur.x=point[w].x;
    cur.y=point[w].y;
    memset(used,-1,sizeof(used));
    used[cur.x][cur.y]=0;
    q.push(cur);
    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.x>=n || next.y<0 || next.y>=m) continue;
            if (str[next.x][next.y]=='x') continue;
            if (used[next.x][next.y]==-1)
            {
                used[next.x][next.y]=used[cur.x][cur.y]+1;
                q.push(next);
                if (str[next.x][next.y]>='a' && str[next.x][next.y]<'o')
                    dis[w][str[next.x][next.y]-'a'+1]=dis[str[next.x][next.y]-'a'+1][w]=used[next.x][next.y];
            }
        }
    }
}

int main()
{
    int i,j,ii,ans,k;
    b[0]=0;
    b[1]=1;
    for (i=2;i<=15;i++)
        b[i]=b[i-1]*2;

    while (scanf("%d%d",&m,&n)!=EOF)
    {
        if (n+m==0) break;
        for (i=0;idp[i][j]+dis[j][k]) && dp[i][j]!=-1 && dis[j][k]!=-1)
                        dp[i|b[k]][k]=dp[i][j]+dis[j][k];
                }
        ans=inf;
        for (i=1;i<=cnt;i++)
            if (dp[aim][i]!=-1)
            ans=Min(ans,dp[aim][i]);
        if (ans==inf) printf("-1\n");
        else printf("%d\n",ans);    }
    return 0;
}