Posted on 2008-04-18 00:26
Fox 阅读(4001)
评论(8) 编辑 收藏 引用 所属分类:
T技术碎语
Author: Fox
晚上没有加班，打游戏打到9点过，后面就又看了一道《编程之美》的题目《中国象棋将帅问题》。
题目：下过中国象棋的朋友都知道，双方的“将”和“帅”相隔遥远，并且它们不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子（如图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所有合法位置。要求在代码中只能使用一个变量。
在纸上画了半天，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炫耀。但上面的思路应该比较清晰了，也不管书上的答案了，反正我感觉我这点代码效率应该也不会低到哪儿吧:-)？