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

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

阅读量：5274 次

发布时间：2019-06-14

本文共 2466 字，大约阅读时间需要 8 分钟。

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

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

测试代码：

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 110#define M 200using 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<
          
           =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
           
            >1)&num[j]))continue; //i-1行 int Max=-1; for(int l=0; 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

转载于:https://www.cnblogs.com/s1124yy/p/5520983.html

你可能感兴趣的文章