Posted on 2008-04-18 00:26
Fox 阅读(3990)
评论(8) 编辑 收藏 引用 所属分类:
T技术碎语
Author: Fox
晚上没有加班,打游戏打到9点过,后面就又看了一道《编程之美》的题目《中国象棋将帅问题》。
题目:下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-3所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”):
![1-3副本](http://book.csdn.net/BookFiles/656/img/image003.jpg)
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所有合法位置。要求在代码中只能使用一个变量。
在纸上画了半天,Soft从台湾给带的长寿都让我抽完了,总算对得起这会儿工夫……
我的思路大致如下:
1) 只能使用一个变量nNum ==> 只能使用一个循环,nNum只能用来表示A、B位置的组合,nNum最大为9×9-1=80;
2) 如何用nNum表示一个A、B位置的组合?
下图表示A(红色)、B(蓝色)所在位置:
6 |
7 |
8 |
3 |
4 |
5 |
0 |
1 |
2 |
6 |
7 |
8 |
3 |
4 |
5 |
0 |
1 |
2 |
以nNum%9表示A的位置,nNum/9表示B的位置,如nNum==15,A==6,B==1。
3) 如何确定A、B位置的合法性?
规则都指定了,合法性的确定也就很简单了:A%3 != B%3。
OK,剩下的输出就很简单了,为了好看一点,这里希望直接按题目给的图表示出A、B的位置,如:“A:d10, B:e3”,还有颜色:D。
A的行号:A/3+8;
A的列号:A%3+d;
B的行号:B/3+1;
B的列号:B%3+d;
代码如下(注释掉的部分只是为了输出更“漂亮”一点):
1 #include <stdio.h>
2 //#include <windows.h>
3
4 //HANDLE hStdout;
5 //CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
6 //WORD wOldColorAttrs;
7
8 int _tmain(int argc, _TCHAR* argv[])
9 {
10 //hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
11 //GetConsoleScreenBufferInfo(hStdout, &csbiInfo);
12 //wOldColorAttrs = csbiInfo.wAttributes;
13
14 int nNum = 81; // nNum表示所有位置(含非法),故nNum = 3 * 3 * 3 * 3
15 while( nNum-- )
16 {
17 if( nNum%9%3 != nNum/9%3 )
18 {
19 //SetConsoleTextAttribute(hStdout, FOREGROUND_RED | FOREGROUND_INTENSITY);
20 printf("A:%x%02d ", nNum%9%3+0xd, nNum%9/3+8);
21 //SetConsoleTextAttribute(hStdout, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
22 printf("B:%x%02d ", nNum/9%3+0xd, nNum/9/3+1);
23 }
24 if( !(nNum%9) )
25 printf("\n");
26 };
27 printf("\n");
28 //SetConsoleTextAttribute(hStdout, wOldColorAttrs);
29 return 0;
30 }
输出:
点击查看更清晰原图:D
PS: 刚写完,没有来得及总结更多,急着向LP炫耀。但上面的思路应该比较清晰了,也不管书上的答案了,反正我感觉我这点代码效率应该也不会低到哪儿吧:-)?