编程之美中1.2节讲了将帅问题。问题描述如下:
下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-3所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”):
A、B二子被限制在己方3×3的格子里运动。例如,在如上的表格里,A被正方形{d10,
f10, d8, f8}包围,而B被正方形{d3,
f3, d1, f1}包围。每一步,A、B分别可以横向或纵向移动一格,但不能沿对角线移动。另外,A不能面对B,也就是说,A和B不能处于同一纵向直线上(比如A在d10的位置,那么B就不能在d1、d2以及d3)。
请写出一个程序,输出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++) { // 相关操作 } }
这个方法既简单又直观,不用管那么复杂的位操作。