「USACO3.2」Magic Squarest题解
-题目大意
给定初始二维数组(也即是题中所说的魔板):
1 2 3 4
8 7 6 5
并提供以下3种操作：
\(A\).交换上下两行;
\(B\).将最右边的一行移动到最左边;
\(C\).顺时针旋转魔板的中央4个数字
询问最少多少次操作后，可以转换得到题目要求的序列，并输出字典序最小的操作
-思路
首先，因为这道题并没有一个很清晰的转换方向，所以我们采用bfs来记录当前的状态.
struct node{
int s[10]/*当前的状态*/, val/*当前转换次数*/;
string ans/*当前进行的操作*/;
};
那么，对于每一种操作，我们只需要模拟即可。因为题目要求字典序最小，我们使用bfs要满足第一次搜到的就最小，那么必须是以\(A\)、\(B\)、\(C\)的顺序模拟。
需要注意的是，因为初始的序列是二维，最后求的序列是一维，所以我们可以将二维改成一维方便模拟
也就是:
{1, 2, 3, 4, 5, 6, 7, 8}
而不是:
{1, 2, 3, 4, 8, 7, 6, 5}
对于操作\(A\)， 我们可以:
for(int i = 1, l = 8; i <= 4; i++, l--) swap(w.s[i], w.s[l]);
/*模拟交换上下两行的数字*/
对于操作\(B\)， 我们也可以:
int a = w.s[4], b = w.s[5];/*提取出最右边两行的数字*/
w.s[1] = a;/*将第一排最后一个数放到第一位*/
for(int i = 2; i <= 4; i++) w.s[i] = nex.s[i - 1];/*补齐第一排*/
for(int i = 6; i <= 8; i++) w.s[i - 1] = nex.s[i];/*补齐第二排*/
w.s[8] = b;/*将第二排最后一个数放到第一位*/
对于操作\(C\)， 我们还可以:
swap(w.s[3], w.s[6]), swap(w.s[3], w.s[7]), swap(w.s[2], w.s[3]);
这是什么意思呢? 让我们来模拟一下：
这样就实现了逆时针旋转的效果
最后为了防止重复操作，我们需要判重。
因为一共只有\(8\)个数字，那么只用开\(7\)维数组就够了，因为最后一维一定是固定的。
-\(Code\)(无坑)
#include<bits/stdc++.h>
using namespace std;
struct node{
int s[10], val;
string ans;
}g;/*结构体记录状态*/
int k[10] = {0}/*题目要求的结构*/, vis[10][10][10][10][10][10][10] = {0}/*7维判重数组*/, first[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8}/*初始值*/;
queue<node>p;
inline void check(node w, char ch){
if(!vis[w.s[1]][w.s[2]][w.s[3]][w.s[4]][w.s[5]][w.s[6]][w.s[7]]){
w.ans += ch, w.val++, vis[w.s[1]][w.s[2]][w.s[3]][w.s[4]][w.s[5]][w.s[6]][w.s[7]] = 1;
p.push(w);
}
return;
}/*判重*/
int main(){
for(int i = 1; i <= 8; i++){
scanf("%d", &k[i]);
g.s[i] = first[i];
}
g.val = 0;
p.push(g);/*初始化*/
while(!p.empty()){
node nex = p.front();
p.pop();
int flag = 1;
for(int i = 1; i <= 8; i++){
if(k[i] != nex.s[i]){
flag = 0;
break;
}
}
if(flag){/*判断是否找到结果*/
cout << nex.val << " " << nex.ans;
/*找到即输出*/
break;
}
/*A操作*/
flag = 1;
node w = nex;
for(int i = 1, l = 8; i <= 4; i++, l--) swap(w.s[i], w.s[l]);
check(w, 'A');
/*B操作*/
w = nex;
int a = w.s[4], b = w.s[5];
w.s[1] = a;
for(int i = 2; i <= 4; i++) w.s[i] = nex.s[i - 1];
for(int i = 6; i <= 8; i++) w.s[i - 1] = nex.s[i];
w.s[8] = b;
check(w, 'B');
/*c操作*/
w = nex;
swap(w.s[3], w.s[6]), swap(w.s[3], w.s[7]), swap(w.s[2], w.s[3]);
check(w, 'C');
}
return 0;
}
最终程序仅用时\(10ms\)!可喜可贺!