算法：棋子移动问题

本文主要是介绍算法：棋子移动问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：
设有2n+2个排成一排的格子，最左边两个格子是空的，其后的格子一次放入A子和B子：

现规定移动规则如下：每次可将任意两个相邻的棋子移入空格，移动时两子的左右顺序不得变动，试按此规则以最少的步骤将n个A子移动到一起，n个B子移动到一起，空格的位置可任意。
实现思路

实现代码

public class SortAB{public static void main(String args[]){//通过控制台输入字符串长度int num = 3;java.util.Scanner cin = new java.util.Scanner(System.in);System.out.println("请输入AB的个数:");num = cin.nextInt();char[] AB = generatorAB(num);print(AB,0);sort(AB);}/***将交叉排列的棋子合并*/public static void sort(char[] ab){int length = ab.length;if(length <= 6)return ;int count = 1;//前5个的移动move(ab,3,0,count++);move(ab,1,3,count++);move(ab,5,1,count++);int i = 8;int a = 4;int n = 5;//后面的移动while(i < length){if((a+1) != n){move(ab, a+1, n,count++);n = a+1;}move(ab, i, n,count++);a++;n = i;i = i+2;}//把开头的两个B移动到空白处move(ab,0,n,count++);}/*** 将AB数组中from处相邻的两个字符移动到to相邻的位置处*/private static void move(char[] AB, int from, int to,int count){//from处是否为空if((AB[from] == ' ') ||( AB[from + 1] == ' ')){System.out.println(from + "处不完全是字符！");return;}//判断to处是否为空if((AB[to] != ' ') || (AB[to + 1] != ' ')){System.out.println(to + "处不完全是空格！");return;}//判断越界if((from >= AB.length - 1) || (to >= AB.length - 1 )){System.out.println("越界！");return;}//将form处移动到to处并将from处置空AB[to] = AB[from];AB[to + 1] = AB[from + 1];AB[from] = ' ';AB[from + 1] = ' ';//打印字符列print(AB,count);}/** * 打印字符列*/private static void print(char[] ab,int count){System.out.print(count + ":");for(char c : ab)System.out.print(c);System.out.println();}/*** 产生AB字符列*/private static char[] generatorAB(int n){char[] ab = new char[2 * n + 2];ab[0] = ' ';ab[1] = ' ';for(int i = 2; i < 2 * n + 1; i++){ab[i] = 'A';ab[++i] = 'B';}return ab;}}

运行结果

结果分析
这个移动过程肯定是满足要求的，效率也比较高。但是步数(2n-3)是不是最少的，就不好说了。。。。。需要后面验证一下。。

这篇关于算法：棋子移动问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---