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

发表于2026-03-09|更新于2026-03-09|题解

|浏览量:

用 BFS。

思路

我们可以使用一个长度为 $3\times3$ 的 string 来表示状态，每一种状态可以进行旋转（左上，右上，左下，右下）。
我们可以用 map 来记录状态。
预处理一下即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<string,int> mp; int T,n; char c;
signed main(){
	cin>>T; queue<string> q; //bfs
	q.push("123456789"),mp["123456789"]=1;
	while(q.size()){
		string u=q.front(),v[4]={u,u,u,u}; q.pop();
		v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][8]=u[7];
		v[2][3]=u[4],v[2][4]=u[7],v[2][6]=u[3],v[2][7]=u[6];
		v[1][1]=u[2],v[1][2]=u[5],v[1][4]=u[1],v[1][5]=u[4];
		v[0][0]=u[1],v[0][1]=u[4],v[0][3]=u[0],v[0][4]=u[3];
		for(int i=0;i<4;i++) if(!mp[v[i]]){
			mp[v[i]]=mp[u]+1;if(v[i]=="0123456789")break;q.push(v[i]);
		}
	}while(T--){
		string s;
		for(int i=0;i<9;i++) cin>>c,s+=c;
		cout<<mp[s]-1<<'\n';
	}return 0;
}

文章作者: heyZzz

文章链接: https://heyzzz629.github.io/2026/03/09/%E9%A2%98%E8%A7%A3%EF%BC%9AP10578-%E8%93%9D%E6%A1%A5%E6%9D%AF-2024-%E5%9B%BD-A-%E6%97%8B%E8%BD%AC%E4%B9%9D%E5%AE%AB%E6%A0%BC/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 heyZzz's OI Blog！

相关推荐

题解：P11601 『Fwb』狼人の杀戮

比较烦的中模拟。注意事项：猎人死时必须带走一个人。女巫只有一份毒药和解药。在同一晚，同一位女巫只能做一次操作。如果错误撤回当晚所有操作。操作：我们维护十个数组： $die$，所有死亡的记录。 $nw1$，女巫的毒药操作。 $nw2$，女巫的解药操作。 $nd$，当晚死亡人数。 $nnw$，当晚女巫的操作。 $lr$，当晚狼人的操作。 $er$，猎人带走的操作。 $die1$，$die$ 的副本。 $nw1_1$，$nw1$ 的副本。 $nw2_1$，$nw2$ 的副本。然后，几个 $\texttt {if}$ 判断一下：判断是否出界。判断是否死亡。如果是猎人或女巫，要判断是否当晚死亡。如果是狼人或女巫，要判断是否当晚用。接着，记录死亡，是否用技能： 12345678910111213141516if(op==0){ //狼人 if(a[x]==1&&!die[x]&&!die[y]&&!lr[x]&&x<=n&&x&&y<...

题解：P10043 [CCPC 2023 北京市赛] 广播

线性 DP。不难想到 $dp_{i,j}$ 代表在 $a$ 中前 $i$ 个数和 $b$ 中前 $j$ 个数满足要求。状态转移方程是：边界：如果 $i=m$，$dp_{i,j+1}=\min{dp_{i,j}}$。如果 $j=n$，$dp_{i+1,j}=\min{dp_{i,j}}$。之后： $a_{i+1}=b_{j+1}$ 或者 $a_{i+1}=1$ 或者 $b_{j+1}=1$，$dp_{i+1,j+1}=\min{dp_{i,j}}$。最后 $dp_{i+1,j}=\min{dp_{i,j}+1},dp_{i,j+1}=\min{dp_{i,j}+1}$。代码楼上楼下都已经写的很明白了，我就不在赘述了。

题解：P10161 [DTCPC 2024] 小方的疑惑 10

思路我们注意到答案串一定是若干个可以变成一个可以做出 $k$ 个合法的括号序列的长度 $\le n$ 的序列再补上若干个 )。显然，设答案串 $s$ 有 $k$ 对括号在最外层，那么合法子串个数为 $\frac{k(k+1)}{2}$。我们就可以构造了！这样就可以在不浪费括号的情况下将答案串分成多个括号串。设 $dp_i$ 为构造出 $i$ 个合法子串（即 $k$）所需的最小括号对数。状态转移就是：$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$。我们先把这部分预处理出来。如果 $2dp_k>n$ 则说明无解，否则在 dp 数组上递归构造（如果$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$，那么就转移）。代码： 1234567891011121314151617#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,k,dp[100005];void print(int x){ if(!x) return; ...

题解：CF333B Chips

原题传送门题目大意：有一个 $n \times n$ 的棋盘，$m$ 个格子是障碍物，然后移动芯片使它们返回到初始对边位置，不能经过障碍物、重叠或交换位置。问最多可以放置多少个芯片完成游戏。思路：本题直接按题意模拟即可：使用桶记录障碍，$a_i$ 代表第 $i$ 行的芯片个数，同理 $b_i$ 代表第 $i$ 列的芯片个数。如果第 $i$ 行或第 $j$ 没有芯片，$cnt+1$。如果相遇，就是 $n$ 为奇数且中间行且列有值，$cnt-1$。下面是样例 $3$ 的解释：列1 列2 列3 列4 行1 无芯片可放芯片可放芯片无芯片行2 放芯片 ______ ______ 放芯片行3 障碍物障碍物障碍物可放芯片行4 无芯片可放芯片可放芯片无芯片行2的两个芯片可以连通，$cnt=1$。没有相遇情况，输出 $1$。上代码： 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int n,m,x,y...

题解：P10928 走廊泼水节

回顾 kruskal：取边权最小的一条边，若两个点在不同连通块（并查集），则连边合并。我们把以上规则改一下：如果点 $A$ 的老大的小弟数<点 $B$ 的老大的小弟数，$A$ 成为 $B$ 小弟。反之，$B$ 成为 $A$ 小弟。我们定义 $s_i$ 是点 $i$ 的老大的小弟数，$w$ 是 $a$ 到 $b$ 的边权。贡献和为：$(s_A×s_B−1) \times (w+1)$。代码楼上楼下都已经写的很明白了，我就不在赘述了。

题解：CF1598D Training Session

题目翻译：给定 $n$ 个互不相同二元组，现在要从其中选出三个二元组，使得这三个二元组的的前一项互不相同或后一项互不相同。求有几种方案。思路：正难则反，先算总数：有 $\Large\frac{n \times (n-1) \times (n-2)}{6}$ 种情况。不满足的情况是没有一个二元组与另一个二元组元素两两不相同（同一个元素）。也就是就是一个二元组与另一个二元组元素至少一个相同（也是同一个元素）。考虑用桶记录，$x_i$ 代表 $a_i$ 的出现个数，$y_i$ 代表 $b_i$ 的出现个数。第一组固定，第二组有 $x_{a_i}-1$ 种，第三组有 $y_{b_i}-1$ 种。一共有 $(x_{a_i}-1) \times (y_{b_i}-1)$。代码楼上楼下都已经写的很明白了，我就不在赘述了。