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

题目描述

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

例如

1 2 3
4 5 6
7 8 9

将其旋转右上角，可得：

1 5 2
4 6 3
7 8 9

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

1 2 3
4 5 6
7 8 9

输入格式

输入的第一行包含一个整数 $T$ 表示询问的组数。

接下来依次输入每组询问。

每组询问包含三行，每行包含三个数，表示询问的九宫格的状态。

输出格式

输出 $T$ 行，每行包含一个整数表示本次询问的答案。

输入输出样例 #1

输入 #1

2
1 2 3
4 5 6
7 8 9
1 5 2
4 6 3
7 8 9

输出 #1

0
3

说明/提示

对于 $60\%$ 的评测用例，$T=1$;
对于所有评测用例，$T\le 10^5$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int t;
char c;
string a = "123456789";
queue<string> q;
map<string, int> mp;
void bfs(){
    q.push(a), mp[a] = 0;
    while (!q.empty())    {
        string s = q.front();
        q.pop();
        a = s, a[0] = s[1], a[1] = s[4], a[3] = s[0], a[4] = s[3];
        if (!mp.count(a))
            mp[a] = mp[s] + 1, q.push(a);
        a = s, a[1] = s[2], a[2] = s[5], a[4] = s[1], a[5] = s[4];
        if (!mp.count(a))
            mp[a] = mp[s] + 1, q.push(a);
        a = s, a[3] = s[4], a[4] = s[7], a[6] = s[3], a[7] = s[6];
        if (!mp.count(a))
            mp[a] = mp[s] + 1, q.push(a);
        a = s, a[4] = s[5], a[5] = s[8], a[7] = s[4], a[8] = s[7];
        if (!mp.count(a))
            mp[a] = mp[s] + 1, q.push(a);
    }
}
int main(){
    scanf("%d", &t), bfs();
    while (t--)    {
        a = "";
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                scanf(" %c", &c), a += c;
        printf("%d\n", mp[a]);
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容