棋子换位

有n个棋子A，n个棋子B，在棋盘上排成一行。 它们中间隔着一个空位，用“.”表示，比如：

AAA.BBB

现在需要所有的A棋子和B棋子交换位置。 移动棋子的规则是：

1. A棋子只能往右边移动，B棋子只能往左边移动。
2. 每个棋子可以移动到相邻的空位。
3. 每个棋子可以跳过相异的一个棋子落入空位（A跳过B或者B跳过A）。

AAA.BBB 可以走法： 移动A ==> AA.ABBB 移动B ==> AAAB.BB

跳走的例子： AA.ABBB ==> AABA.BB

以下的程序完成了AB换位的功能，请仔细阅读分析源码，填写划线部分缺失的内容。

#include <stdio.h>
#include <string.h>

void move(char* data, int from, int to)
{
	data[to] = data[from];
	data[from] = ‘.‘;
}

int valid(char* data, int k)
{
	if(k<0 || k>=strlen(data)) return 0;
	return 1;
}
	
void f(char* data)
{
	int i;
	int tag;
	int dd = 0; // 移动方向
	
	while(1){
		tag = 0;
		for(i=0; i<strlen(data); i++){
			if(data[i]==‘.‘) continue;
			if(data[i]==‘A‘) dd = 1;
			if(data[i]==‘B‘) dd = -1;
			
			if(valid(data, i+dd) && valid(data,i+dd+dd) 
			&& data[i+dd]!=data[i] && data[i+dd+dd]==‘.‘){ 
			//如果能跳... 
				move(data, i, i+dd+dd);
				printf("%s\n", data);
				tag = 1;
				break;
			}
		}
		
		if(tag) continue;
		
		for(i=0; i<strlen(data); i++){
			if(data[i]==‘.‘) continue;
			if(data[i]==‘A‘) dd = 1;
			if(data[i]==‘B‘) dd = -1;			
				 
			if(valid(data, i+dd) && data[i+dd]==‘.‘){ 
			// 如果能移动...
				if( (25分) ) continue;  //填空位置 
				move(data, i, i+dd);
				printf("%s\n", data);
				tag = 1;
				break;
			}
		}
		
		if(tag==0) break;					
	}
}
	
int main()
{
	char data[] = "AAA.BBB";	
	f(data);
	return 0;
}

注意：只提交划线部分缺少的代码，不要复制已有代码或填写任何多余内容。

首先搞清楚题意一开始AAA.BBB要求变成BBB.AAA，具体可以怎么操作题目说的很清楚，而且还给加了注释，填空位置显然是移动到相邻位置不可行的情况需要跳过，不妨先模拟一下看看，一开始是AAA.BBB，第一步先走A或B无异，假如先走A，为AA.ABBB,接下来有两个走法即A.AABBB和AABA.BB,显然前一种已经无法走下去了，除了移动A别无选择，所以我们继续看后面的情况，仍然接下去有两个走法，AAB.ABB和AABAB.B,对前一种来说可以移动A为A.BAABB,最右边的两个B永远也到不了左边，也可以移动B为AABBA.B,左边的A也被堵住了，也不行，因此这种走法错误，这样差不多能找到规律了，想要移动到相邻的位置，得确保前面第二个位置的字符和后面第一个位置的字符得不相同，不然就不行。

棋子换位

原文：https://www.cnblogs.com/8023spz/p/10546134.html