Stoney's Blog

编程之美 1.2 中国象棋将帅问题 Supporting tagline

# 题意

中国象棋中，“将”和“帅”相隔遥远，并且不能照面。为了方便，用A、B分别表示“将”和“帅”。

A、B在各自的3x3的格子里移动，每次移动一步，可以横向或纵向移动，不能沿对角线移动。A、B不能移出各自的格子，不能同时出现在同一条纵向直线上。

写出一个程序，输出A、B所有的合法位置。要求只能用一个字节存储变量。

# 思路1

A、B各自的移动空间是3x3的格子，横向三个位置，纵向三个位置。而一个字节有8位。可以将一个字节拆分成四个部分，每个部分两位，分别表示A的纵向位置、A的横向位置、B的纵向位置、B的横向位置。

但是两位二进制具有四个状态，因此需要在状态改变时判断，如果到达11状态，使其加1，跳过该状态。

字节使用分配

移动时，使字节最低位自加，相当于B在横向位置上移动。自加的进位表示纵向移动，进位后变回00表示横向上回到初始位置。

程序结束的状态是10101010，即A、B的纵横位置均到达第三位置。

void cnChess(){
	unsigned char x = 0x0;

	while(x <= 0xaa){	//10101010
		if((x&0x0c) != ((x&0xc0)>>4)){    
			printf("(%d, %d) (%d, %d)\n",
			(x&0xc0)>>6, (x&0x30)>>4,   //A vertical	A horizontal
			(x&0x0c)>>2, x&0x03);       //B vertical	B horizontal
		}

		++x;
		if((x&0x03) == 0x03) //00000011
			x += 0x01;
		if((x&0x0c) == 0x0c) //00001100
			x += 0x04;
		if((x&0x30) == 0x30) //00110000
			x += 0x10;
		if((x&0xc0) == 0xc0) //11000000
			x += 0x40;
	}
}

# 思路2

A、B各自具有9个状态，A和B的状态组合共81种。而一个字节共有256种状态，足够存储A、B的状态信息。

void cnChess2(){
	unsigned char i = 0;
	while(i < 81){
		if(i/9%3 != i%9%3){
			printf("(%d, %d) (%d, %d)\n", i/9%3, i/9/3, i%9/3, i%9%3);
		}
		++i;
	}
}
blog comments powered by Disqus

Published

05 April 2016

Tags