魔板 (bfs+康托展开)
2024-09-05 14:54:05
# 10027. 「一本通 1.4 例 2」魔板
【题目描述】
Rubik 先生在发明了风靡全球魔方之后,又发明了它的二维版本——魔板。这是一张有 888 个大小相同的格子的魔板:
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。这 8 种颜色用前 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于上图的魔板状态,我们用序列 $1,2,3,4,5,6,7,8$ 来表示。这是基本状态。
这里提供三种基本操作,分别用大写字母 A
,B
,C
来表示(可以通过这些操作改变魔板的状态):
A
:交换上下两行;B
:将最右边的一列插入最左边;C
:魔板中央作顺时针旋转。
下面是对基本状态进行操作的示范:
A
:
8 7 6 5
1 2 3 4
B
:
4 1 2 3
5 8 7 6
C
:
1 7 2 4
8 6 3 5
对于每种可能的状态,这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。
【算法】
显然使用bfs,新知识点:cantor展开。注意魔板的输入顺序是顺时针。
【代码】
#include <bits/stdc++.h>
using namespace std;
int d[50010],rec[50010][2];
const int fac[]={ 1,1,2,6,24,120,720,5040,40320 };
struct state{ int now[2][4]; }st,ed;
queue<state> q;
int cantor(state& x) {
int tmp[8],res=0;
for(int i=0;i<2;i++)
for(int j=0;j<4;j++)
tmp[i*4+j]=x.now[i][j];
for(int i=0;i<8;i++) {
int s=0;
for(int j=i+1;j<8;j++) if(tmp[j]<tmp[i]) s++;
res+=s*fac[7-i];
}
return res;
}
void print(int x) {
if(x==cantor(st)) return;
print(rec[x][1]);
printf("%c",char(rec[x][0]));
}
int main() {
for(int i=0;i<4;i++) st.now[0][i]=i+1,scanf("%d",&ed.now[0][i]);
for(int i=0;i<4;i++) st.now[1][3-i]=4+i+1,scanf("%d",&ed.now[1][3-i]);
for(int i=0;i<=fac[8];i++) d[i]=-1;
d[cantor(st)]=0; q.push(st);
while(q.size()) {
state now=q.front(),tmp; q.pop();
if(cantor(now)==cantor(ed)) break;
//A
for(int i=0;i<2;i++) {
for(int j=0;j<4;j++)
tmp.now[(i+1)%2][j]=now.now[i][j];
}
if(d[cantor(tmp)]==-1) {
d[cantor(tmp)]=d[cantor(now)]+1;
rec[cantor(tmp)][0]='A';
rec[cantor(tmp)][1]=cantor(now);
q.push(tmp);
}
//B
tmp.now[0][0]=now.now[0][3],tmp.now[1][0]=now.now[1][3];
for(int i=0;i<2;i++) {
for(int j=0;j<3;j++)
tmp.now[i][j+1]=now.now[i][j];
}
if(d[cantor(tmp)]==-1) {
d[cantor(tmp)]=d[cantor(now)]+1;
rec[cantor(tmp)][0]='B';
rec[cantor(tmp)][1]=cantor(now);
q.push(tmp);
}
//C
memcpy(tmp.now,now.now,sizeof(now.now));
tmp.now[0][1]=now.now[1][1]; tmp.now[0][2]=now.now[0][1];
tmp.now[1][1]=now.now[1][2]; tmp.now[1][2]=now.now[0][2];
if(d[cantor(tmp)]==-1) {
d[cantor(tmp)]=d[cantor(now)]+1;
rec[cantor(tmp)][0]='C';
rec[cantor(tmp)][1]=cantor(now);
q.push(tmp);
}
}
printf("%d\n",d[cantor(ed)]);
print(cantor(ed));
return 0;
}
最新文章
- C#针对js escape解码
- String,你到底创建了几个对象????
- Quartz之CronExpression
- OpenShare文档管理不完整功能清单
- FC网络学习笔记01
- jquery 移除数组重复的元素----$.unique()
- sd卡文件操作
- 史上最全常用正则表达式(Javascript公众号推文)
- Redis详解(一)------ redis的简介与安装
- 用SQL表达交并差操作
- [USACO11DEC]牧草种植Grass Planting
- Oracle笔记----oracle数字类型number自增
- File类 详解!
- Linux系统下用find命令查找最近修改过的文件
- UML速记
- 超强、超详细Redis入门教程【转】
- Day 9 作业题(完成)
- spring中的context:include-filter和context:exclude-filter的区别
- linux 监控文件变化
- 装好Linux后没有声音的看过来
热门文章
- js倒计时功能中newData().getTime()在iOS下会报错,显示 nan
- 一、创建并打包Cordova的App工程
- 039:模版结构优化之include标签详解
- 【leetcode】299. Bulls and Cows
- 快速掌握Eclipse Plugin / RCP开发思想
- pytest-生成测试报告
- Java——容器(List)
- [BZOJ2225][SPOJ2371]LIS2 - Another Longest Increasing Subsequence Problem:CDQ分治+树状数组+DP
- Redis实现存取数据+数据存取
- 职位-CIO:CIO