P1259 黑白棋子的移动 【洛谷算法习题】

P1259 黑白棋子的移动网页链接P1259 黑白棋子的移动题目描述有2 n 2n2n个棋子排成一行开始为位置白子全部在左边黑子全部在右边如下图为n 5 n5n5的情况移动棋子的规则是每次必须同时移动相邻的两个棋子颜色不限可以左移也可以右移到空位上去但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子不能平移要求最后能移成黑白相间的一行棋子。如n 5 n5n5时成为任务编程打印出移动过程。输入格式一个整数n nn。输出格式若干行表示初始状态和每次移动的状态用o \verb!o!o表示白子* \verb!*!*表示黑子- \verb!-!-表示空行。输入输出样例 #1输入 #17输出 #1ooooooo*******-- oooooo--******o* oooooo******--o* ooooo--*****o*o* ooooo*****--o*o* oooo--****o*o*o* oooo****--o*o*o* ooo--***o*o*o*o* ooo*o**--*o*o*o* o--*o**oo*o*o*o* o*o*o*--o*o*o*o* --o*o*o*o*o*o*o*说明/提示4 ≤ n ≤ 100 4\leq n\leq 1004≤n≤100解题思路本题核心是递归分治 状态模拟按照固定规则完成黑白棋子的移动变换。初始状态为n个白子、n个黑子后接两个空位目标是排成黑白相间的序列。采用递归解法设定n4为递归基例执行固定的5步移动完成转换当n4时先执行两步统一的移动操作将问题规模缩小为n-1再递归处理子问题。用字符串数组模拟棋子与空位的状态移动函数实现相邻两子移至空位的规则操作每一步移动后打印当前棋盘状态完整输出所有移动过程完美适配题目规则与数据范围。总结核心逻辑递归分治拆解大问题基例固定步骤通用步骤结合完成棋子移动。关键操作数组模拟棋盘状态、移动函数实现规则换位、递归调用缩小问题规模。效率保障递归逻辑简洁模拟操作直观严格匹配题目输出格式与移动要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll sp,n;string c[206];voidp(){for(ll i1;i2*n2;i)coutc[i];coutendl;}voidmv(ll k){for(ll j0;j1;j){c[spj]c[kj];c[kj]-;}spk;p();}voidf(ll k){if(k4){mv(4);mv(8);mv(2);mv(7);mv(1);}else{mv(k);mv(2*k-1);f(k-1);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);for(ll i1;in;i)c[i]o;for(ll in1;i2*n;i)c[i]*;c[2*n1]-;c[2*n2]-;sp2*n1;p();f(n);return0;}