87.黑白子交換
有三個(gè)白子和三個(gè)黑子如下圖布置：
○ ○ ○ . ● ● ●
游戲的目的是用最少的步數(shù)將上圖中白子和黑子的位置進(jìn)行交換：
● ● ● . ○ ○ ○
游戲的規(guī)則是：(1)一次只能移動(dòng)一個(gè)棋子； (2)棋子可以向空格中移動(dòng)，也可以跳過一個(gè)對(duì)方的棋子進(jìn)入空格，但不能向后跳，也不能跳過兩個(gè)子。請(qǐng)用計(jì)算機(jī)實(shí)現(xiàn)上述游戲。
*問題分析與算法設(shè)計(jì)
計(jì)算機(jī)解決勝這類問題的關(guān)鍵是要找出問題的規(guī)律，或者說是要制定一套計(jì)算機(jī)行動(dòng)的規(guī)則。分析本題，先用人來解決問題，可總結(jié)出以下規(guī)則：
(1) 黑子向左跳過白子落入空格，轉(zhuǎn)(5)
(2) 白子向右跳過黑子落入空格，轉(zhuǎn)(5)
(3) 黑子向左移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)象)，轉(zhuǎn)(5)
(4) 白子向右移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)萌)，轉(zhuǎn)(5)
(5) 判斷游戲是否結(jié)束，若沒有結(jié)束，則轉(zhuǎn)(1)繼續(xù)。
所謂的“阻塞”現(xiàn)象就是：在移動(dòng)棋子的過程中，兩個(gè)尚未到位的同色棋子連接在一起，使棋盤中的其它棋子無法繼續(xù)移動(dòng)。例如按下列方法移動(dòng)棋子：
0
○ ○ ○ . ● ● ●
1 ○ ○ . ○ ● ● ●
2 △ ○ ○ ● ○ . ● ●
3
○ ○ ● . ○ ● ●
4 兩個(gè)●連在一起產(chǎn)生阻塞
○ ○ ● ● ○ . ●
或4 兩個(gè)白連在一起產(chǎn)生阻塞
○ . ● ○ ○ ● ●
產(chǎn)生阻塞的現(xiàn)象的原因是在第2步(△狀態(tài))時(shí)，棋子○不能向右移動(dòng)，只能將●向左移動(dòng)。
總結(jié)產(chǎn)生阻塞的原因，當(dāng)棋盤出現(xiàn)“黑、白、空、黑”或“白、空、黑、白”狀態(tài)時(shí)，不能向左或向右移動(dòng)中間的棋子，只移動(dòng)兩邊的棋子。
按照上述規(guī)則，可以保證在移動(dòng)棋子的過程中，不會(huì)出現(xiàn)棋子無法移動(dòng)的現(xiàn)象，且可以用最少的步數(shù)完成白子和黑子的位置交換。
*程序與程序注釋
#include
int number;
void print(int a[]);
void change(int *n,int *m);
void main()
{
int t[7]={1,1,1,0,2,2,2}; /*初始化數(shù)組1：白子 2：黑子 0：空格*/
int i,flag;
print(t);
while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=3) /*判斷游戲是否結(jié)束
若還沒有完成棋子的交換則繼續(xù)進(jìn)行循環(huán)*/
{
flag=1; /*flag 為棋子移動(dòng)一步的標(biāo)記1：尚未移動(dòng)棋子 0：已經(jīng)移動(dòng)棋子*/
for(i=0;flag&&i<5;i++) /*若白子可以向右跳過黑子，則白子向右跳*/
if(t[i]==1&&t[i+1]==2&&t[i+2]==0)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<5;i++) /*若黑子可以向左跳過白子，則黑子向左跳*/
if(t[i]==0&&t[i+1]==1&&t[i+2]==2)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<6;i++) /*若向右移動(dòng)白子不會(huì)產(chǎn)生阻塞,則白子向右移動(dòng)*/
if(t[i]==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2]))
{change(&t[i],&t[i+1]); print(t);flag=0;}
for(i=0;flag&&i<6;i++) /*若向左移動(dòng)黑子不會(huì)產(chǎn)生阻塞，則黑子向左移動(dòng)*/
if(t[i]==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2]))
{ change(&t[i],&t[i+1]); print(t);flag=0;}
}
}
void print(int a[])
{
int i;
printf("No. %2d:.............................\n",number++);
printf(" ");
for(i=0;i<=6;i++)
printf(" | %c",a[i]==1?'*':(a[i]==2?'@':' '));
printf(" |\n .............................\n\n");
}
void change(int *n,int *m)
{
int term;
term=*n; *n=*m; *m=term;
}
有三個(gè)白子和三個(gè)黑子如下圖布置：
○ ○ ○ . ● ● ●
游戲的目的是用最少的步數(shù)將上圖中白子和黑子的位置進(jìn)行交換：
● ● ● . ○ ○ ○
游戲的規(guī)則是：(1)一次只能移動(dòng)一個(gè)棋子； (2)棋子可以向空格中移動(dòng)，也可以跳過一個(gè)對(duì)方的棋子進(jìn)入空格，但不能向后跳，也不能跳過兩個(gè)子。請(qǐng)用計(jì)算機(jī)實(shí)現(xiàn)上述游戲。
*問題分析與算法設(shè)計(jì)
計(jì)算機(jī)解決勝這類問題的關(guān)鍵是要找出問題的規(guī)律，或者說是要制定一套計(jì)算機(jī)行動(dòng)的規(guī)則。分析本題，先用人來解決問題，可總結(jié)出以下規(guī)則：
(1) 黑子向左跳過白子落入空格，轉(zhuǎn)(5)
(2) 白子向右跳過黑子落入空格，轉(zhuǎn)(5)
(3) 黑子向左移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)象)，轉(zhuǎn)(5)
(4) 白子向右移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)萌)，轉(zhuǎn)(5)
(5) 判斷游戲是否結(jié)束，若沒有結(jié)束，則轉(zhuǎn)(1)繼續(xù)。
所謂的“阻塞”現(xiàn)象就是：在移動(dòng)棋子的過程中，兩個(gè)尚未到位的同色棋子連接在一起，使棋盤中的其它棋子無法繼續(xù)移動(dòng)。例如按下列方法移動(dòng)棋子：
0
○ ○ ○ . ● ● ●
1 ○ ○ . ○ ● ● ●
2 △ ○ ○ ● ○ . ● ●
3
○ ○ ● . ○ ● ●
4 兩個(gè)●連在一起產(chǎn)生阻塞
○ ○ ● ● ○ . ●
或4 兩個(gè)白連在一起產(chǎn)生阻塞
○ . ● ○ ○ ● ●
產(chǎn)生阻塞的現(xiàn)象的原因是在第2步(△狀態(tài))時(shí)，棋子○不能向右移動(dòng)，只能將●向左移動(dòng)。
總結(jié)產(chǎn)生阻塞的原因，當(dāng)棋盤出現(xiàn)“黑、白、空、黑”或“白、空、黑、白”狀態(tài)時(shí)，不能向左或向右移動(dòng)中間的棋子，只移動(dòng)兩邊的棋子。
按照上述規(guī)則，可以保證在移動(dòng)棋子的過程中，不會(huì)出現(xiàn)棋子無法移動(dòng)的現(xiàn)象，且可以用最少的步數(shù)完成白子和黑子的位置交換。
*程序與程序注釋
#include
int number;
void print(int a[]);
void change(int *n,int *m);
void main()
{
int t[7]={1,1,1,0,2,2,2}; /*初始化數(shù)組1：白子 2：黑子 0：空格*/
int i,flag;
print(t);
while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=3) /*判斷游戲是否結(jié)束
若還沒有完成棋子的交換則繼續(xù)進(jìn)行循環(huán)*/
{
flag=1; /*flag 為棋子移動(dòng)一步的標(biāo)記1：尚未移動(dòng)棋子 0：已經(jīng)移動(dòng)棋子*/
for(i=0;flag&&i<5;i++) /*若白子可以向右跳過黑子，則白子向右跳*/
if(t[i]==1&&t[i+1]==2&&t[i+2]==0)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<5;i++) /*若黑子可以向左跳過白子，則黑子向左跳*/
if(t[i]==0&&t[i+1]==1&&t[i+2]==2)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<6;i++) /*若向右移動(dòng)白子不會(huì)產(chǎn)生阻塞,則白子向右移動(dòng)*/
if(t[i]==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2]))
{change(&t[i],&t[i+1]); print(t);flag=0;}
for(i=0;flag&&i<6;i++) /*若向左移動(dòng)黑子不會(huì)產(chǎn)生阻塞，則黑子向左移動(dòng)*/
if(t[i]==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2]))
{ change(&t[i],&t[i+1]); print(t);flag=0;}
}
}
void print(int a[])
{
int i;
printf("No. %2d:.............................\n",number++);
printf(" ");
for(i=0;i<=6;i++)
printf(" | %c",a[i]==1?'*':(a[i]==2?'@':' '));
printf(" |\n .............................\n\n");
}
void change(int *n,int *m)
{
int term;
term=*n; *n=*m; *m=term;
}