hdu 5067 網絡賽 狀態壓縮 或dfs

hdu 5067 網絡賽 狀態壓縮 或dfs

題意是給你n*m的方格 裡面有最多10個格子有數 問你最少走多少步能將所有的數字移到左上角 能無限裝下數字

這裡介紹兩種做法 dfs和狀態壓縮dp

1 dfs

由於每個數字之間是一定可以到達的 所有只用考慮走有數字的情況 最多10！種情況 找到做小的就行 果斷的深搜 注意下優化

#include
#include
#include
using namespace std;

struct node
{
    int x,y;
}leap[20];
int abs(int a)
{
    return a<0?-a:a;
}
int map[55][55],k,Min,visit[20];
int dfs(int step,int num,int x,int y)
{
    int i;
    if(step>Min) return 0;
    if(num==k)
    {
        if(step+x-1+y-1<Min)
        Min=step+x-1+y-1;
        return 0;
    }
    for(i=1;i<=k;i++)
    {
        if(visit[i]) continue;
        visit[i]=1;
        dfs(step+abs(leap[i].x-x)+abs(leap[i].y-y),num+1,leap[i].x,leap[i].y);
        visit[i]=0;
    }
    return 0;
}
int main()
{
    int i,j,n,m;
    while(~scanf("%d%d",&n,&m))
    {
        k=0;
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j])
            {
                leap[++k].x=i;
                leap[k].y=j;
            }
        }
        Min=99999999;
        memset(visit,0,sizeof(visit));
        dfs(0,0,1,1);
        if(k==0) printf("0\n");
        else 
        printf("%d\n",Min);
    }
    return 0;
}

這裡的點只針對有數字的點

共10種狀態 dp【i】【j】表示狀態i裡走到j這個點的最少步數 dis表示每個點之間所需要的步數

#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f 

int min(int a,int b)
{
    return a<b?a:b;
}
struct node
{
    int x,y;
}leap[15];
int abs(int a)
{
    return a<0?-a:a;
}
int cont(int a, int b)
{
    return abs(leap[a].x-leap[b].x)+abs(leap[a].y-leap[b].y);    
}
int dp[5000][15];
int main()
{
    int i,j,n,m,a;
    while(~scanf("%d%d",&n,&m))
    {
        int k=0;
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a);
            if(a)
            {
                leap[++k].x=i;
                leap[k].y=j;
            }
        }
        leap[0].x=leap[0].y=1;
        int state=1<<(k+1);
        memset(dp,INF,sizeof(dp));
        int dis[15][15];
        for(i=0;i<=k;i++)
        for(j=i;j<=k;j++)
        dis[i][j]=dis[j][i]=cont(i,j);
        dp[1][0]=0;
        for(i=1;i<state;i++)
        {
            for(j=0;j<=k;j++)
            {
                if(dp[i][j]==INF) continue;
                for(int z=0;z<=k;z++)
                {
                    if(i&(1<<z)) continue;
                    dp[i|(1<<z)][z]=min(dp[i|(1<<z)][z],dp[i][j]+dis[j][z]);
                }
            }
        }
        int Min=9999999;
        for(i=0;i<=k;i++)
        if(dp[state-1][i]+dis[i][0]<Min) Min=dp[state-1][i]+dis[i][0];
        printf("%d\n",Min);
    }    
    return 0;
}