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

arcmiao · 2025-03-03 21:26:46 · 题解

BFS

思路

• 本题如果从每一个起点开始 bfs 到终点，在 10^5 次询问下毫无疑问会 TLE，这时我们考虑从终点预处理出到所有可能情况的步数

• 本题选择用一个长度为 ⑨ 的 string 来表示每一种状态，对于一种状态有四种旋转方式（详细见代码），这里用 map<string,int> 来记录到每一种状态的步数

• 接着在询问前做一个从终点开始的 bfs 即可，能以 O(1) 的时间复杂度输出答案

AC Code

#include <bits/stdc++.h>
using namespace std;
string t="123456789";
map<string,int> h; 
void bfs()
{
    queue<string> q;
    q.push(t);
    h[t]=1;
    while(q.size())
    {
        string u=q.front();
        q.pop();
        string v[4]= {u,u,u,u};
        v[0][0]=u[1],v[0][1]=u[4],v[0][3]=u[0],v[0][4]=u[3]; // 左上角
        v[1][1]=u[2],v[1][2]=u[5],v[1][4]=u[1],v[1][5]=u[4]; // 右上角
        v[2][3]=u[4],v[2][4]=u[7],v[2][6]=u[3],v[2][7]=u[6]; // 左下角
        v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][8]=u[7]; // 右下角
        // 注意这是一个逆推的过程，要逆时针转
        for(int i=0; i<4; i++)
            if(!h[v[i]])
            {
                h[v[i]]=h[u]+1;
                if(v[i]==t) break;
                q.push(v[i]);
            }
    }
}

int main()
{
    int _=1;
    scanf("%d",&_);
    bfs(); // 从终点开始预找出所有可能结果的步数
    while(_--)
    {
        string s;
        for(int i=0; i<9; i++)
        {
            char c;
            scanf(" %c",&c);
            s+=c;
        }
        printf("%d\n",h[s]-1);
    }
    return 0;
}

望审核大大通过！ ๐•ᴗ•๐