Posted on 2008-04-18 00:26
Fox 閱讀(4017)
評論(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炫耀。但上面的思路應該比較清晰了，也不管書上的答案了，反正我感覺我這點代碼效率應該也不會低到哪兒吧:-)？