109徐守佳

用户名：dotcpp0787174

访问量：1120

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	876
经　　验	3560
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[蓝桥杯2017年第八届真题-油漆面积] 扫描线
浏览：42

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：60

[信息学奥赛一本通T1247-河中跳房子] 二分答案
浏览：53

你可能喜欢

[蓝桥杯2024年第十五届决赛真题-旋转九宫格] 测试数据量最大的一集

　　作者: 109徐守佳　　　　发表时间：2024-09-16 16:49:54 浏览：497　|　评论：3　

原题链接：蓝桥杯2024年第十五届决赛真题-旋转九宫格

### 思路:
在不超时的范围以下从终点开始找出所有的答案(9!种),最后以O1的速度输出答案
不然10^5的数据量绝对不行(本蒟蒻已试过单向BFS,双向BFS,A*,通通TLE)

```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
#define PIS pair<int,string>
using namespace std;
const int N = 510 + 5,M = 31 * 1e5 + 10,inf = 0x3f3f3f3f;

int g[3][3]; 
int note[3][3]; //用于复原
unordered_map<string,int> dist; //记录全部答案到达的步数
void unturn(int k,int l) //逆时针旋转操作,根据k和l的值变动转轴
{
    for(int i=k;i<k+2;i++)
    {
        for(int j=l;j<l+2;j++)
        {
            if(k==0&&l==0) g[i][j] = note[j][1-i];
            if(k==0&&l==1) g[i][j] = note[j-1][2-i];
            if(k==1&&l==0) g[i][j] = note[j+1][2-i];
            if(k==1&&l==1) g[i][j] = note[j][3-i];      
        }
    }
}
void getnum(string str) //获取当前的九宫格状态
{
    int cnt = 0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            g[i][j] = str[cnt++] - '0';
        }
    }
}
string getstr() //获取九宫格对应的字符串
{
    string s;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            s += g[i][j] + '0';
        }
    }
    return s;
}
void bfs()
{
    int total = 362880; //九宫格的所有排列只有9!种,全部找出即可
    int cnt = 0; 
    string ed = "123456789";
	//从终点状态开始往四周找出各个状态的步数
    queue<string> q;
    q.push(ed);
    dist[ed] = 0; //初始步数0
    while (q.size())
    {
        if(cnt > total) return; //找完了退出
        auto t = q.front();
        q.pop();
        getnum(t); //获取当前九宫格
        memcpy(note,g,sizeof note); //复制给note后面用于复原
        for(int k=0;k<2;k++) 
		//分别从左上,右上,左下,右下逆时针转一次
            for(int l=0;l<2;l++)
            {
                memcpy(g,note,sizeof g); 
				//每转动的时候复原成初态note再转
                unturn(k,l); //逆时针转一次
                string n = getstr();  //获取当前九宫格的字符状态
                if(dist.count(n)) continue; //以前出现过就叉出去
                dist[n] = dist[t] + 1; //记录到达这个状态的步数
                q.push(n); //加入队列继续找
                cnt++; //排列种数+1
            }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    bfs(); //提前找出所有可能的答案
    while (T--)
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                cin>>g[i][j];
            }
        }
        string ans = getstr(); //获取当前输入的九宫格的字符状态
        cout<<dist[ans]<<endl; //以O1的速度输出答案
    }
    return 0;
}
```
![](https://pic.imgdb.cn/item/66f65b83f21886ccc0deb063.gif)

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yxy

/ ￣￣￣＼　 
|　ー　ー \　 
|　 ◉　◉ |   / ￣￣￣￣￣￣＼
\ 　 ▱　 / ∠ 不要卷了，             \ 
  ＼       イ      \         徐sj !!!    /
 ／　   　＼     \______________/
/　|　　  \ \　 
|　|　　　 | |

2024-09-17 15:51:43

yxy

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀⠛⠿⠿⣿⠃⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀⠀⠙⢿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇⠀⠀⠀⠀⠀
⠀⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇⠀⠀⠀⠀⠀⠀
⠀⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀

2024-09-17 01:03:31

yxy

%%%%%% orz

2024-09-16 19:39:56

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C二级辅导-同因查找（C语言代码）

[蓝桥杯2024年第十五届决赛真题-旋转九宫格] 测试数据量最大的一集

评论区

精彩推荐

C二级辅导-阶乘数列（C语言代码）

母牛的故事（C语言代码）

蛇行矩阵（C语言代码）

wu-理财计划（C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

母牛的故事（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

核桃的数量（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-分段函数（C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C二级辅导-同因查找 （C语言代码）

[蓝桥杯2024年第十五届决赛真题-旋转九宫格] 测试数据量最大的一集

评论区

精彩推荐

C二级辅导-阶乘数列 （C语言代码）

母牛的故事 （C语言代码）

蛇行矩阵 （C语言代码）

wu-理财计划 （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

母牛的故事 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

核桃的数量 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-分段函数 （C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

C二级辅导-阶乘数列（C语言代码）

母牛的故事（C语言代码）

蛇行矩阵（C语言代码）

wu-理财计划（C++代码）

母牛的故事（C语言代码）

核桃的数量（C语言代码）

C二级辅导-分段函数（C语言代码）