信息学奥赛一本通 1327：【例7.6】黑白棋子的移动
【题目链接】
ybt 1327：【例7.6】黑白棋子的移动
【题目释义】
- 开始时，末尾有两个空位可以使用。
- 棋子移动后，会在原位置留有空位，相隔空位的两个棋子不算相邻。
- 每次必须移动相邻棋子，可以是同色的也可以是不同色的，只能将这两个棋子移动到空位。
- 移动棋子必须跳过一些棋子，不可以平移。
【题目考点】
1. 递归
【解题思路】
- 首先要知道，当n=4时，左侧4个白棋，右侧4个黑棋，此时有固定的最少的移动方法，5步后可以完成移动。
- 如果n>4，左侧n个白棋，右侧n个黑棋，那么每次将中间的白黑两棋子移动到空位，再将两个黑棋移动到空位，使得当前面对的情况为左侧n-1个白棋，右侧n-1个黑棋，这是原问题的子问题，可以递归解决。
【题解代码】
解法1：递归
#includeusing namespace std;char c[1005];//c[i]:第i位置的字符 int n, b, step;//b：左侧空位下标void show(){ cout << "step" << setw(2) << step << ':'; for(int i = 1; i <= 2*n+2; ++i)//2n个棋子加上2个空位 cout << c[i]; cout << endl; step++;}void move(int i)//将i与i+1位置的棋子移动到b与b+1位置 { swap(c[i], c[b]); swap(c[i+1], c[b+1]); b = i;}void solve(int k)//将下标1~k为白棋，k+1~2*k为黑棋的情况移动成黑白相间的情况 { if(k == 4) { int a[] = {4,8,2,7,1};//最后5步移动为：4 8 2 7 1 for(int i = 0; i < 5; ++i) { move(a[i]); show(); } return; } move(k);//中间的白棋黑棋移动到最后 show(); move(2*k-1);//末尾的两个黑棋移动到中间 show(); solve(k-1);//解决左边k-1个白棋右边k-2个黑棋的情况 }int main(){ cin >> n; for(int i = 1; i <= n; ++i) { c[i] = 'o'; c[i+n] = '*'; } b = 2*n+1;//一开始空位在末尾 c[b] = c[b+1] = '-'; show(); solve(n); return 0;}
