题解：P10578 [蓝桥杯 2024 国 A] 旋转九宫格

LinkGTF · 2025-05-12 21:07:41 · 题解

题意

给定一个 3\times 3 的九宫格，每个格子内分别含有一个数字，每个格子里的数字互不相同。每步我们可以选择任意一个 2\times 2 的区域将其顺时针旋转。

问最少需要几步才能将给定的状态旋转为

1 2 3
4 5 6
7 8 9

思路

考虑 bfs。

状态存一个长度为 9 的 vector v 依次表示第一行第一列、第一行第二列......第三行第三列。

存一个二维数组 r，第一维表示转的是 0 (左上)、1 (右上)、2 (左下) 还是 3 (右下) 的 2\times 2 区域。里面存的是顺时针旋转该 2\times 2 区域前后的相对位置。

拿右上举例，原来的位置为

1 2 3
4 5 6
7 8 9

顺时针旋转之后位置变成了

1 5 2
4 6 3
7 8 9

这时只需要在开一个 vector v2 将原数组的位置 j 复制到新数组的 r_{i,j} 位置，其中 i 表示转的是哪个区域，即 v2_{r_{i,j}}=v_j。

AC代码

#include <bits/stdc++.h>
using namespace std;

vector<int> s, e;
map<vector<int>, int> dis;
int r[4][9] = {{3, 0, 2, 4, 1, 5, 6, 7, 8}, {0, 4, 1, 3, 5, 2, 6, 7, 8}, {0, 1, 2, 6, 3, 5, 7, 4, 8}, {0, 1, 2, 3, 7, 4, 6, 8, 5}};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 1; i <= 9; i++){
        s.emplace_back(i);
    }
    while(t--){
        e.clear();
        for(int i = 1; i <= 9; i++){
            int x;
            cin >> x;
            e.emplace_back(x);
        }
        queue<vector<int>> q;
        q.push(s);
        dis[s] = 1;
        while(!q.empty()){
            vector<int> x = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                vector<int> t(9);
                for(int j = 0; j < 9; j++){
                    t[r[i][j]] = x[j];
                }
                if(!dis[t]){
                    dis[t] = dis[x] + 1;
                    q.push(t);
                }
            }
        }
        cout << dis[e] - 1 << '\n';
    }
    return 0;
}