P1225

题目

题目描述：

黑白棋游戏的棋盘由 4×44 \times 4 方格阵列构成。棋盘的每一方格中放有 11 枚棋子，共有 88 枚白棋子和 88 枚黑棋子。这 1616 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 11 条公共边的 22 个方格称为相邻方格。一个方格最多可有 44 个相邻方格。在玩黑白棋游戏时，每一步可将任何 22 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

输入格式：

输入文件共有 88 行。前四行是初始游戏状态，后四行是目标游戏状态。每行 44 个数分别表示该行放置的棋子颜色。“ 00 ”表示白棋；“ 11 ”表示黑棋。

输出格式：

输出文件的第一行是着棋步数 nn。接下来 nn 行，每行 44 个数分别表示该步交换棋子的两个相邻方格的位置。例如，abcd 表示将棋盘上 (a,b)(a,b) 处的棋子与 (c,d)(c,d) 处的棋子换位。

数据范围与说明：

由 @zhouyonglong 提供 SPJ

输入输出样例 #1

输入：

1
2
3
4
5
6
7
8
1111
0000
1110
0010
1010
0101
1010
0101

输出：

1
2
3
4
5
4
1222
1424
3242
4344

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int f[5005][5005],len=1;
void func(int x){
    for(int i=1;i<=len;i++){
        f[x][i]=f[x-1][i]+f[x-2][i];
    }
    for(int i=1;i<=len;i++){
        if(f[x][i]>=10){
            f[x][i+1]+=f[x][i]/10;
            f[x][i]%=10;
            while(f[x][len+1]){
                len++;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    f[1][1]=1;
    f[2][1]=2;
    for(int i=3;i<=n;i++){
        func(i);
    }
    for(int i=len;i>=1;i--){
        cout<<f[n][i];
    }
    return 0;
}