信息学奥赛一本通T1327-黑白棋子的移动

解题思路:递归， 4以下写的很苦， 不优化了

注意事项:格式

参考代码:

#include<iostream>
#include<limits>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
char a[N];
int m; 
void print(int i){
	printf("step%2d:",i); 
	for(int i = 1; i <= 2 * m + 2; i ++){
		cout << a[i];
	}
	cout << endl;
}
void dfs(int n,int l){
	if(n > 4){
		a[2*n + 1] = a[n];
		a[2*n + 2] = a[n + 1];
		a[n] = a[n + 1] = '-';
		print(l++);
		a[n] = a[2 * n - 1];
		a[n + 1] = a[2 * n - 2];
		a[2 * n - 1] = a[2* n ] = '-';
		print(l++);		
		dfs(n - 1, l);
	}
	if(n == 4){

		a[2*n + 1] = a[n];
		a[2*n + 2] = a[n + 1];
		a[n] = a[n + 1] = '-';
		print(l++);
		a[n] = a[2 * n ];
		a[n + 1] = a[2 * n + 1];
		a[2 * n] = a[2* n + 1] = '-';
		print(l++);
		
		a[2*n] = a[n- 2];
		a[2*n + 1] = a[n- 1];
		a[n-2] = a[n - 1] = '-';
		print(l++);
		n--;
		a[n-1] = a[2*n + 1];
		a[n] = a[2*n + 2];
		a[2*n + 1] = a[2*n + 2] = '-'; 
		print(l ++); 
				
		a[2*n + 1] = a[n - 2] ;
		a[2*n + 2] = a[n - 1] ;
		a[n - 2] = a[n - 1] = '-';
		print(l ++);
		return;
	}

}
int main()
{

	cin >> m;
	for(int i = 1; i <= m; i ++){
		a[i] = 'o';
		a[i + m] = '*';
	}
	a[2*m + 1] = a[2*m + 2] = '-';
	print(0); 
	dfs(m,1);	
	return 0;
}