编程之美 中国象棋将帅问题 位操作

编程之美中1.2节讲了将帅问题。问题描述如下：

下过中国象棋的朋友都知道，双方的“将”和“帅”相隔遥远，并且它们不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子（如图1-3所示）（为了下面叙述方便，我们约定用A表示“将”，B表示“帅”）：

A、B二子被限制在己方3×3的格子里运动。例如,在如上的表格里，A被正方形{d₁₀, f₁₀, d₈, f₈}包围，而B被正方形{d₃, f₃, d₁, f₁}包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B，也就是说，A和B不能处于同一纵向直线上（比如A在d₁₀的位置，那么B就不能在d₁、d₂以及d₃）。

请写出一个程序，输出A、B所有合法位置。要求在代码中只能使用一个变量。

 

因为只能用一个变量，所以就要通过位操作来保存足够的信息。将一个byte类型的变量的左边4位和右边4位保存不同的信息。

位操作请参照：http://blog.csdn.net/weixingstudio/article/details/6787628 虽然这里的位操作是C#的，但是C++的位操作原理一样。

 

因为只可以使用一个变量，所以在for 循环中也只可以使用为操作来记录信息。

一下是详细代码，代码中注释可以详细的了解原理。

// chess.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream"

#define HALF_BITS_LENGTH 4
// 记录存储单元长度的一般
#define FULLMASK 255  // 记录完全的mask
#define LMASK (FULLMASK<<HALF_BITS_LENGTH) // 表示左侧的mask, 1111 0000
#define RMASK (FULLMASK>>HALF_BITS_LENGTH) // 右侧的mask, 0000 1111
#define RSET(b,n) (b=(LMASK&b)|n)  // 将b的右侧设置成n
#define LSET(b,n) (b=(RMASK&b)|(n<<HALF_BITS_LENGTH)) // 将b的左侧设置成n
#define RGET(b) (RMASK&b) // 获得b的右侧
#define LGET(b) ((LMASK&b)>>HALF_BITS_LENGTH) // 获得b的左侧
#define GRID 3

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned char b;
    for(LSET(b,1);LGET(b)<=GRID*GRID;LSET(b,(LGET(b)+1)))
    {
        for(RSET(b,1);RGET(b)<=GRID*GRID;RSET(b,(RGET(b)+1)))
        {
            if(LGET(b)%GRID!=RGET(b)%GRID)
            {
                printf("A=%d, B=%d \n", LGET(b),RGET(b));
            }
        }
    }
    return 0;
}

 

 

 

当然，如果不用位操作也可以，还有人提出了可以这样做，通过结构体来操作。

struct
{
    unsigned char a:4;
    unsigned char b:4;
}i;

for(i.a=1;i.a<=9;i.a++)
{
    for(i.b=1;i.b<=9;i.b++)
    {
        // 相关操作
    }
}

这个方法既简单又直观，不用管那么复杂的位操作。