问题描述

本题是一个基于“Gap”纸牌游戏的搜索问题。我们需要通过一系列合法的移动操作，将初始的纸牌布局转换为目标布局。目标布局要求每一行的纸牌按照花色递增的顺序排列。我们需要找到最少的移动次数，或者判断无法达到目标布局。

输入输出格式

• 输入：
  • 第一行是一个整数 a，表示初始布局的数量。
  • 接下来是 a 组数据，每组数据由五行组成：
    • 第一行是空行。
    • 接下来的四行，每行包含七个两位数，表示初始布局的纸牌。
• 输出：
  • 对于每个初始布局，输出一行，表示达到目标布局所需的最少移动次数。如果无法达到目标布局，输出 -1。

解题思路

1. 数据结构设计：

   • 使用一个二维数组 c[10][10] 来存储纸牌的布局，其中 c[i][0] 表示第 i 行的空位。
   • 使用一个结构体 wolf 来表示当前的纸牌布局状态，方便在搜索过程中存储和比较状态。

2. 预处理：

   • 将数值为 1 的纸牌移动到每行的最左边，形成初始的“Gap”布局。
   • 检查是否已经满足目标布局，如果是，则直接输出 0。

3. 搜索算法：

   • 使用广度优先搜索（BFS）来寻找从初始布局到目标布局的最短路径。
   • 使用队列 Q 存储当前状态和对应的移动次数。
   • 使用集合 S 存储已经访问过的状态，避免重复搜索。

4. 状态转移：

   • 对于每个空位，尝试用其左边邻居的后继纸牌填充该空位。
   • 如果后继纸牌存在且合法，则生成新的状态并加入队列。

5. 目标检测：

   • 检查当前状态是否满足目标布局，即每一行的纸牌是否按照花色递增的顺序排列。
   • 如果满足目标布局，输出当前的移动次数并结束搜索。

6. 特殊情况处理：

   • 如果队列为空且仍未找到目标布局，则输出 -1。

代码解析

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

// 定义一个结构体表示当前的纸牌布局
struct wolf {
    int c[4][8]; // 4 行，每行 8 列（包括空位）
};

// 重载结构体的比较运算符，用于 set 中的去重
inline bool operator<(const wolf &a, const wolf &b) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 8; j++) {
            if (a.c[i][j] != b.c[i][j]) {
                return a.c[i][j] < b.c[i][j]; // 按字典序比较
            }
        }
    }
    return false;
}

int main() {
    int a;
    cin >> a; // 读取初始布局的数量
    while (a--) {
        wolf initial; // 定义初始状态
        // 读取初始布局
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j < 8; j++) {
                cin >> initial.c[i][j]; // 跳过空位，从第 2 列开始读取纸牌
            }
        }
        // 初始化空位
        for (int i = 0; i < 4; i++) {
            initial.c[i][0] = 11 + i * 10; // 每行的空位编号为 11, 21, 31, 41
        }

        // 移除数值为 1 的纸牌，放置到每行的最左边
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j < 8; j++) {
                if (initial.c[i][j] % 10 == 1) { // 如果纸牌的数值为 1
                    initial.c[i][j] = 0; // 将该位置设为空
                }
            }
        }

        // 初始化队列和集合
        queue<pair<wolf, int> > Q; // 队列用于 BFS，存储当前状态和移动次数
        set<wolf> S; // 集合用于存储已经访问过的状态，避免重复搜索
        Q.push(make_pair(initial, 0)); // 将初始状态和移动次数 0 加入队列
        S.insert(initial); // 将初始状态加入集合

        bool found = false; // 标记是否找到目标布局
        while (!Q.empty()) {
            wolf current = Q.front().first; // 当前状态
            int cost = Q.front().second; // 当前移动次数
            Q.pop();

            // 检查是否达到目标布局
            bool is_goal = true;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 7; j++) {
                    if (current.c[i][j] != 11 + i * 10 + j) { // 检查是否满足目标布局
                        is_goal = false;
                        break;
                    }
                }
                if (!is_goal) break;
            }
            if (is_goal) {
                found = true;
                cout << cost << endl; // 输出移动次数
                break;
            }

            // 尝试所有可能的移动
            for (int i = 0; i < 4; i++) {
                for (int j = 1; j < 8; j++) {
                    if (!current.c[i][j] && current.c[i][j - 1] && current.c[i][j - 1] % 10 != 7) {
                        // 如果当前空位的左边有纸牌且该纸牌的数值不是 7
                        int row = -1, col = -1;
                        // 找到后继纸牌的位置
                        for (int k = 0; k < 4; k++) {
                            for (int l = 0; l < 8; l++) {
                                if (current.c[k][l] == current.c[i][j - 1] + 1) {
                                    row = k;
                                    col = l;
                                    break;
                                }
                            }
                            if (row != -1) break;
                        }
                        if (row != -1) {
                            // 生成新的状态
                            wolf next_state = current;
                            next_state.c[row][col] = 0; // 将后继纸牌移出原位置
                            next_state.c[i][j] = current.c[i][j - 1] + 1; // 将后继纸牌移动到当前空位

                            // 检查是否已经访问过
                            if (S.find(next_state) == S.end()) {
                                S.insert(next_state); // 将新状态加入集合
                                Q.push(make_pair(next_state, cost + 1)); // 将新状态加入队列，移动次数加 1
                            }
                        }
                    }
                }
            }
        }

        if (!found) {
            cout << "-1" << endl; // 如果未找到目标布局，输出 -1
        }
    }
    return 0;
}

代码逻辑分析

1. 输入处理：

   • 读取初始布局，并将数值为 1 的纸牌移动到每行的最左边，形成初始的“Gap”布局。

2. BFS 搜索：

   • 使用队列存储当前状态和对应的移动次数。
   • 使用集合存储已经访问过的状态，避免重复搜索。
   • 对于每个状态，尝试所有可能的移动操作，生成新的状态并加入队列。

3. 目标检测：

   • 检查当前状态是否满足目标布局，即每一行的纸牌是否按照花色递增的顺序排列。
   • 如果满足目标布局，输出当前的移动次数并结束搜索。

4. 特殊情况处理：

   • 如果队列为空且仍未找到目标布局，则输出 -1。

时间复杂度分析

• 每个状态最多有 4 * 7 = 28 种可能的移动操作。
• 使用集合 S 去重，避免重复搜索。
• 最坏情况下，状态空间的大小为 8!（每行有 8 个位置，每行的纸牌排列方式），因此时间复杂度为 O(8! * 28)。

总结

本题是一个典型的搜索问题，通过广度优先搜索（BFS）可以找到从初始布局到目标布局的最短路径。关键在于设计合适的数据结构来存储状态，并通过集合去重来避免重复搜索。