HDU 4539 郑厂长系列故事――排兵布阵(曼哈顿距离)

这虽然是中文题，然而没看懂，不懂的地方，就是在曼哈顿距离这块，网上搜索了一下，写了个程序，是测试曼哈顿距离的。

曼哈顿距离：两点（x1,y1）（x2,y2）的曼哈顿距离为|x1-x2|+|y1-y2|

测试代码：

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

typedef unsigned long long ull;

#define fi first

#define se second

#define prN printf("\n")

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

char tu[60][60];

int a[100][2];

int main()

{

#ifndef ONLINE_JUDGE

//    freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);

//    freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);

#endif // ONLINE_JUDGE

    int i=2,i1=3;

    int p=0;

    rep(j,6)

    rep(j1,6)

    {

        if (abs(i-j)+abs(i1-j1)==2)

        {

            printf("%d %d\n",j,j1);

            a[p][0]=j;

            a[p++][1]=j1;

        }

    }

//     i=2,i1=2;

//    rep(j,6)

//    rep(j1,6)

//    {

//        if (abs(i-j)+abs(i1-j1)==2)

//        {

//            printf("%d %d\n",j,j1);

//            a[p][0]=j;

//            a[p++][1]=j1;

//        }

//    }

    cle(tu,'.');

    rep(i,p)

    {

        tu[a[i][0]][a[i][1]]='*';

    }

    rep(i,6)

    {

        rep(j,6)

        {

            printf("%c ",tu[i][j]);

        }

        prN;

    }

    return 0;

}

这是根据测试样例的背景写的，i，i1是所给坐标，最后输出*的地方，就是他对应的曼哈顿距离（由图可知：曼哈顿距离就是以这个点为中心的菱形）

AC代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define N 110

#define M 200

using namespace std;

int n,m,a[N];

int dp[N][M][M],cnt,num[M],sum[M];

///dp[i][j][k]  表示第i行的j状态 i-1行的k状态 的最优解

bool ok(int x)

{

    return (x&(x<<2))||(x&(x<<2));///第x-2个和x+2个位是否有人，

    // 有的话就不符合条件

}

int getsum(int x)    ///1的个数，即放多少个兵

{

    int sum=0;

    while(x)

    {

        if(x&1)sum++;

        x>>=1;

    }

    return sum;

}

void init()

{

    cnt=0;

    for(int i=0; i<(1<<m); i++)   ///预处理，压缩

    {

        if(!ok(i))

        {

            num[cnt]=i;

            sum[cnt++]=getsum(i);

        }

    }

}

////二进制函数

//int two[100];

//void o_two(int n)

//{

//    memset(two,0,sizeof(two));

//    int p=1;

//    while(n)

//    {

//        two[p++]=n%2;

//        n/=2;

//    }

//    printf("Two:");

//    for (int i=12;i>=1;i--)

//    {

//        if (i%4==0)

//            printf("  ");

//        printf("%d ",two[i]);

//    }puts("");

//}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);

//    freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);

#endif // ONLINE_JUDGE

    while(~scanf("%d%d",&n,&m))

    {

        memset(a,0,sizeof a);

        for(int i=0; i<n; i++)

        {

            for(int j=0; j<m; j++)

            {

                int x;

                scanf("%d",&x);

                if(x)continue;///方便计算，把0存为1

                a[i]|=(1<<j);

            }

        }

//        for (int i=0;i<n;i++)

//            o_two(a[i]);

        init();///初始化了num（情况数组）和sum（个数数组）

        memset(dp,0,sizeof dp);

        for(int i=0; i<cnt; i++)   ///处理第一行

        {

            if(a[0]&num[i])continue;

            dp[0][i][0]=sum[i];

        }

        ///递推，要考虑三行的情况，

        for(int i=1; i<n; i++)   //第一行

        {

            for(int j=0; j<cnt; j++)

            {

                if(a[i]&num[j])continue;   ///第一行与原来矩阵有冲突

                for(int k=0; k<cnt; k++)     ///第二行

                {

                    if(a[i-1]&num[k])continue;

                    if(((num[k]<<1)&num[j])||((num[k]>>1)&num[j]))continue; //i-1行

                    int Max=-1;

                    for(int l=0; l<cnt; l++)         ///第三行

                    {

                        if(num[j]&num[l])continue;

                        if(((num[l]<<1)&num[k])||((num[l]>>1)&num[k]))continue;

                        Max=max(Max,dp[i-1][k][l]);

                    }

                    dp[i][j][k]=Max+sum[j];

                }

            }

        }

        int Max=-1;

        for(int i=0; i<cnt; i++)

            for(int j=0; j<cnt; j++)

                Max=max(Max,dp[n-1][i][j]);

        printf("%d\n",Max);

    }

    return 0;

}

巴特西

HDU 4539 郑厂长系列故事――排兵布阵(曼哈顿距离)

最新文章

热门文章