当前位置：首页 > 蓝桥杯 > 2024年蓝桥杯国赛A组题九宫格全解析：基于BFS算法的代码实现与优化

2024年蓝桥杯国赛A组题九宫格全解析：基于BFS算法的代码实现与优化

3天前

一、题目解读

2024年蓝桥杯国A的九宫格题目（对应洛谷P10578）要求通过旋转九宫格中的2x2区域，实现从初始状态到目标状态的转换，并计算最小步数。该问题属于经典的图论搜索问题，需要高效的状态转换与路径优化，考验算法设计与代码实现能力。

二、解题思路

采用广度优先搜索（BFS）为核心算法，通过以下关键点解决该问题：

1. 状态表示：将3x3矩阵转换为字符串，简化状态存储与比较。

2. 旋转操作：设计旋转函数，对指定2x2区域进行顺时针旋转，避免重复计算。

3. BFS搜索：利用队列存储状态，配合哈希表标记已访问状态，确保无重复遍历。

4. 目标判定：通过字符串比对快速判断是否达到目标状态，减少计算开销。

三、解题步骤

1. 初始化与预处理：

读取输入，将初始矩阵和目标矩阵（1-9顺序排列）转换为字符串形式。

若初始状态即为目标，直接返回0步。

2. BFS搜索流程：

入队初始状态，标记为已访问。

循环遍历队列：

取出当前状态，尝试对所有可能的2x2区域（共4个）进行旋转。

生成新状态并转换为字符串，若为目标状态则返回步数+1。

若新状态未访问过，标记并加入队列，步数+1。

若遍历结束未找到目标，返回-1（理论上所有状态可解）。

3. 旋转优化：通过临时变量交换法实现顺时针旋转，避免复杂循环，提升效率。

四、代码与注释

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

// 将3x3矩阵转换为字符串表示
string gridToString(const vector<vector<int>>& grid) {
    string s;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            s += to_string(grid[i][j]); // 拼接数字为字符串
    return s;
}

// 旋转2x2区域的函数
vector<vector<int>> rotate(const vector<vector<int>>& grid, int x, int y) {
    vector<vector<int>> newGrid = grid;
    // 顺时针旋转
    int temp = newGrid[x][y];
    newGrid[x][y] = newGrid[x+1][y];
    newGrid[x+1][y] = newGrid[x+1][y+1];
    newGrid[x+1][y+1] = newGrid[x][y+1];
    newGrid[x][y+1] = temp; // 临时变量交换法
    return newGrid;
}

int bfs(const vector<vector<int>>& start) {
    vector<vector<int>> target = {{1,2,3},{4,5,6},{7,8,9}}; // 目标状态
    string targetStr = gridToString(target);
    string startStr = gridToString(start);
    
    if (startStr == targetStr) return 0; // 初始状态即目标
    
    queue<pair<vector<vector<int>>, int>> q; // 队列存储状态与步数
    unordered_map<string, bool> visited; // 标记已访问状态
    
    q.push({start, 0});
    visited[startStr] = true;
    
    while (!q.empty()) {
        auto current = q.front().first;
        int steps = q.front().second;
        q.pop();
        
        // 尝试所有可能的2x2旋转区域
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                vector<vector<int>> next = rotate(current, i, j); // 旋转生成新状态
                string nextStr = gridToString(next);
                
                if (nextStr == targetStr) return steps + 1; // 找到目标直接返回步数
                
                if (!visited[nextStr]) { // 未访问则入队
                    visited[nextStr] = true;
                    q.push({next, steps + 1});
                }
            }
        }
    }
    return -1; // 理论上所有状态都可解
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快输入速度
    
    int T;
    cin >> T;
    while (T--) {
        vector<vector<int>> grid(3, vector<int>(3));
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                cin >> grid[i][j];
        
        cout << bfs(grid) << '\n';
    }
    return 0;
}