2024年蓝桥杯国赛旋转九宫格：BFS最短路径算法完全解析

一、问题重述与难点分析

给定一个3x3数字矩阵，每次操作可以顺时针旋转任意2x2子矩阵，求将初始状态转为目标状态[[1,2,3],[4,5,6],[7,8,9]]的最少操作次数。

核心难点：

1. 状态空间规模达9! = 362880种排列

2. 需要证明所有状态可达性

3. 必须保证找到最短路径

二、完整代码实现（带详细注释）

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

/* 将3x3矩阵转换为9位字符串
   例如：[[1,2,3],[4,5,6],[7,8,9]] → "123456789" */
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子矩阵
   (x,y)表示子矩阵左上角坐标，范围必须∈[0,1] */
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;
}

/* BFS核心算法：返回从start到target的最短步数 */
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();
        
        // 尝试四个可能的旋转区域：(0,0),(0,1),(1,0),(1,1)
        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;
}

三、算法核心思想解析

1. 状态表示：使用字符串压缩存储3x3矩阵，便于哈希处理

2. 状态扩展：每个状态通过4种可能的旋转生成新状态

3. BFS特性：首次到达目标状态时的步数即为最小值

4. 去重机制：哈希表记录已访问状态，避免重复计算

四、复杂度

• 时间复杂度：O(9!×4) 最坏情况需遍历所有状态

• 空间复杂度：O(9!) 需要存储访问记录