洛谷 P1259【黑白棋子的移动】

描述

有2n个棋子（n≥4）排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为n=5的情况：

○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：

○●○●○●○●○●

题目

编程打印出移动过程。

输入输出格式

输入

一个整数n(n<=100)

输出

若干行，表示初始状态和每次移动的状态，用"o"表示白子，"*"表示黑子，"-"表示空行。

输入输出样例

输入样例1

输出样例1

ooooooo*******--
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*

解题思路

　　其实主要就是一种递归的思想，整体来说很简单

　　大致思路就是把n个棋子转换成n-1个棋子做，由于4很特殊

　　所以单独输出；

　　初始化——（向后移——向前移——判断）（循环递归）——暴力枚举——输出

题解

 1 #include<bits/stdc++.h>//万能头文件
 2 using namespace std;
 3 void hou(long long n);
 4 void qian(long long n);
 5 void si(long long n);
 6 void chu(long long n);
 7 void shu(long long x);
 8 char a[100001]; 
 9 bool j=true;
10 long long n,x=0;
11 int main()//主程序（好少）
12 {
13 
14     cin>>n; 
15     chu(n); 
16     return 0;
17 }
18 void chu(long long n)//初始化 
19 {
20     if(j)//赋值一下 
21     {
22         for(int i=1;i<=2*n;i++)//把棋子初始化
23             a[i]='o';
24         for(int i=n+1;i<=2*n;i++)
25             a[i]='*';
26         for(int i=2*n+1;i<=2*n+2;i++)
27             a[i]='-';
28         shu(x);
29         j=false;
30     }
31     if(n==4) si(n); //如果还剩四个，单独输出
32     if(n>4) hou(n); //否则继续操作
33 }
34 void hou(long long n) //向后移
35 {
36     if(a[1]!='-')
37    {  
38     swap(a[n],a[2*n+1]);//交换位置
39     swap(a[n+1],a[2*n+2]);
40     shu(x);    //输出输出 
41     qian(n);//做向前操作
42     } 
43     else return;
44  } 
45 void qian(long long n)//向前移 
46 {
47     swap(a[n],a[2*n-1]);//交换为主
48     swap(a[n+1],a[2*n]);
49     n--;
50     shu(x);//一波输出 
51     chu(n);//一波操作做完判断是否大于4 
52 }
53 void si(long long n)//4单独输出（暴力枚举） 
54 {
55     swap(a[4],a[9]);
56     swap(a[5],a[10]);
57     shu(x);
58     swap(a[4],a[8]);
59     swap(a[5],a[9]);
60     shu(x);
61     swap(a[2],a[8]);
62     swap(a[3],a[9]);
63     shu(x);
64     swap(a[2],a[7]);
65     swap(a[3],a[8]);
66     shu(x);
67     swap(a[1],a[7]);
68     swap(a[2],a[8]);
69     shu(x);
70     return;
71 } 
72 void shu(long long y)//负责输出 
73 {
74     for(int i=1;i<=n*2+2;i++)
75         cout<<a[i];
76     cout<<endl;
77     x++;
78 }

借鉴专用区（大家都懂）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void hou(long long n);
 4 void qian(long long n);
 5 void si(long long n);
 6 void chu(long long n);
 7 void shu(long long x);
 8 char a[100001]; 
 9 bool j=true;
10 long long n,x=0;
11 int main()
12 {
13 
14     cin>>n; 
15     chu(n); 
16     return 0;
17 }
18 void chu(long long n)
19 {
20     if(j)
21     {
22         for(int i=1;i<=2*n;i++)
23             a[i]='o';
24         for(int i=n+1;i<=2*n;i++)
25             a[i]='*';
26         for(int i=2*n+1;i<=2*n+2;i++)
27             a[i]='-';
28         shu(x);
29         j=false;
30     }
31     if(n==4) si(n);
32     if(n>4) hou(n); 
33 }
34 void hou(long long n) 
35 {
36     if(a[1]!='-')
37    {  
38     swap(a[n],a[2*n+1]);
39     swap(a[n+1],a[2*n+2]);
40     shu(x);  
41     qian(n);
42     } 
43     else return;
44  } 
45 void qian(long long n) 
46 {
47     swap(a[n],a[2*n-1]);
48     swap(a[n+1],a[2*n]);
49     n--;
50     shu(x);
51     chu(n);
52 }
53 void si(long long n)
54 {
55     swap(a[4],a[9]);
56     swap(a[5],a[10]);
57     shu(x);
58     swap(a[4],a[8]);
59     swap(a[5],a[9]);
60     shu(x);
61     swap(a[2],a[8]);
62     swap(a[3],a[9]);
63     shu(x);
64     swap(a[2],a[7]);
65     swap(a[3],a[8]);
66     shu(x);
67     swap(a[1],a[7]);
68     swap(a[2],a[8]);
69     shu(x);
70     return;
71 } 
72 void shu(long long y)
73 {
74     for(int i=1;i<=n*2+2;i++)
75         cout<<a[i];
76     cout<<endl;
77     x++;
78 }