A2409. 黑白棋游戏
编程题
提高+/省选-
知识点
题目描述
黑白棋游戏的棋盘由 $4 \times 4$ 方格阵列构成。棋盘的每一方格中放有 $1$ 枚棋子,共有 $8$ 枚白棋子和 $8$ 枚黑棋子。这 $16$ 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 $1$ 条公共边的 $2$ 个方格称为相邻方格。一个方格最多可有 $4$ 个相邻方格。在玩黑白棋游戏时,每一步可将任何 $2$ 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态,编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。
输入格式
输入文件共有 $8$ 行。前四行是初始游戏状态,后四行是目标游戏状态。每行 $4$ 个数分别表示该行放置的棋子颜色。“ $0$ ”表示白棋;“ $1$ ”表示黑棋。
输出格式
输出的是最短着棋步数 $n$。
输入输出样例
输入 #1
1111 0000 1110 0010 1010 0101 1010 0101
输出 #1
4
输入 #2
1101 0000 0000 0001 1001 0000 0000 0110
输出 #2
4
说明/提示
无