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 (a<b) return a;
    else return b;
}

void bfs(int w)
{
    queue<node>q;
    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;i<n;i++)
            scanf("%s",str[i]);
        cnt=0;
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
            if (str[i][j]=='o')
            {
                point[0].x=i;
                point[0].y=j;
            }
            else
            if (str[i][j]=='*')
            {
                cnt++;
                str[i][j]='a'+cnt-1;
                point[cnt].x=i;
                point[cnt].y=j;
            }
        if (cnt==0)
        {
            printf("0n");
            continue;
        }
        memset(dis,-1,sizeof(dis));
        for (i=0;i<cnt;i++)
            bfs(i);
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        aim=b[cnt+1]-1;
        for (ii=1;ii<=10;ii++)
        for (i=0;i<=aim;i++)
            for (j=0;j<=cnt;j++)
            if ((b[j]&i)!=0 || j==0)
                for (k=1;k<=cnt;k++)
                if ((b[k]&i)==0 && k!=j)
                {
                    if ((dp[i|b[k]][k]==-1 || dp[i|b[k]][k]>dp[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("-1n");
        else printf("%dn",ans);    }
    return 0;
}

最后

以上就是踏实萝莉为你收集整理的POJ 2688 BFS+状压DP的全部内容，希望文章能够帮你解决POJ 2688 BFS+状压DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。