有三个白子和三个黑子如下图布置：○ ○ ○ ● ● ●用最少的步数将上图中白子和黑子的位置进行交换：● ● ● ○ ○ ○规则是：（1）一次只能移动一个棋子； （2）棋子可以向空格中移
有三个白子和三个黑子如下图布置：○ ○ ○ ● ● ●用最少的步数将上图中白子和黑子的位置进行交换：● ● ● ○ ○ ○规则是：（1）一次只能移动一个棋子； （2）棋子可以向空格中移
有三个白子和三个黑子如下图布置：
○ ○ ○ ● ● ●
用最少的步数将上图中白子和黑子的位置进行交换：
● ● ● ○ ○ ○
规则是：
（1）一次只能移动一个棋子；
（2）棋子可以向空格中移动,也可以跳过一个对方的棋子进入空格,但不能向后跳,也不能跳过两个子.
（本题共60分,要求1占30分,要求2占30分）
要求：
（1）分析问题,找出规律,总结出规则和算法,并描述你的算法设计思想.
（2）编程显示每一步交换过程.
白子和黑子之间有一个空位的,没有显示出来,不好意思啊
有三个白子和三个黑子如下图布置：○ ○ ○ ● ● ●用最少的步数将上图中白子和黑子的位置进行交换：● ● ● ○ ○ ○规则是：（1）一次只能移动一个棋子； （2）棋子可以向空格中移
/**
* 黑白棋程序入口
*
* @author skr
*
*/
public class HeiBaiQi {
public static void main(String[] args) {
new Run().run();
}
}
/**
* 棋子类,基类
*
* @author skr
*
*/
abstract class QiZi {
/**
* 棋子编号
*/
public int number;
/**
* 棋子所在位置
*/
public int index;
public abstract boolean move(StringBuilder chessboard);
}
/**
* 黑子类继承棋子类
*
* @author skr
*
*/
class HeiZi extends QiZi {
public HeiZi(int num) {
number = num;
}
/**
* 黑子移动方法
*/
public boolean move(StringBuilder chessboard) {
boolean flag = true;
int sIndex = chessboard.indexOf("s");
if (sIndex == index - 1 || sIndex == index - 2) {
chessboard.setCharAt(index, 's');
chessboard.setCharAt(sIndex, 'b');
index = sIndex;
} else
flag = false;
if (chessboard.toString().equals(Run.chessboardEnd))
Run.flag = true;
String strFlag = flag ? "成功" : "失败";
System.out.println("尝试路径：" + Run.routeStr + number + "\t" + chessboard
+ "\t" + strFlag);
return flag;
}
}
/**
* 白子类继承棋子类
*
* @author skr
*
*/
class BaiZi extends QiZi {
public BaiZi(int num) {
number = num;
}
/**
* 白子移动方法
*/
public boolean move(StringBuilder chessboard) {
boolean flag = true;
int sIndex = chessboard.indexOf("s");
if (sIndex == index + 1 || sIndex == index + 2) {
chessboard.setCharAt(index, 's');
chessboard.setCharAt(sIndex, 'w');
index = sIndex;
} else
flag = false;
if (chessboard.toString().equals(Run.chessboardEnd))
Run.flag = true;
String strFlag = flag ? "成功" : "失败";
System.out.println("尝试路径：" + Run.routeStr + number + "\t" + chessboard
+ "\t" + strFlag);
return flag;
}
}
class Run {
/**
* 标志是否找到了最佳路径
*/
public static boolean flag = false;
/**
* 最佳路径字符串
*/
public static StringBuilder routeStr = new StringBuilder();
/**
* 完成时棋盘字符串
*/
public static final String chessboardEnd = "bbbswww";
/**
* 棋盘字符串 b:黑子,s:空格,w:白子
*/
public StringBuilder chessboard = new StringBuilder("wwwsbbb");
/**
* 棋子数组
*/
public QiZi[] qizi = new QiZi[6];
public Run() {
qizi[0] = new BaiZi(0);
qizi[1] = new BaiZi(1);
qizi[2] = new BaiZi(2);
qizi[3] = new HeiZi(3);
qizi[4] = new HeiZi(4);
qizi[5] = new HeiZi(5);
qizi[0].index = 0;
qizi[1].index = 1;
qizi[2].index = 2;
qizi[3].index = 4;
qizi[4].index = 5;
qizi[5].index = 6;
}
/**
* 运行程序,从0步走完开始测试
*/
public void run() {
testRoute();
System.out.println("最佳路径为：" + routeStr);
}
public void testRoute() {
for (int i = 0; i < qizi.length; i++) {
if (flag)
break;
StringBuilder temp = new StringBuilder(chessboard);
int indexTemp = qizi[i].index;
boolean b = qizi[i].move(chessboard);
if (!b)
continue;
if (routeStr.length() != 0
&& i == Integer.parseInt(routeStr.substring(routeStr
.length() - 1)))
continue;
routeStr.append(i);
testRoute();
if (flag)
return;
chessboard = temp;// 还原棋盘
routeStr.deleteCharAt(routeStr.length() - 1);// 还原路径
qizi[i].index = indexTemp;// 还原棋子位置
}
}
}
[楼主,第一版效率较低,我也没时间来考虑优化,仅提供给楼主参考,运行一下几个小时估计可以枚举出结果,楼主可以适当的自己做些优化,比如跳过一些肯定不肯能的情况,可以少很多次迭代,仅供参考,望楼主顺利解决问题 （ 修改了一下,刚才那版有内存溢出的问题）]
经过修改,这个程序效率已经比较高了,上面是我最新修改的,楼主可以拿去试试了
结果（截取）：
尝试路径：23421034521040 bbswbww 失败
尝试路径：23421034521041 bbswbww 失败
尝试路径：23421034521042 bbswbww 失败
尝试路径：23421034521043 bbswbww 失败
尝试路径：23421034521044 bbswbww 失败
尝试路径：23421034521045 bbbwsww 成功
尝试路径：234210345210450 bbbswww 成功
最佳路径为：234210345210450