「一本通 1.4 例 2」[USACO3.2]魔板 Magic Squares
2024-10-20 11:28:49
[USACO3.2]魔板 Magic Squares
题目背景
在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:
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
对于每种可能的状态,这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到目标状态的转换,输出基本操作序列。
输入格式
只有一行,包括8个整数,用空格分开(这些整数在范围 1——8 之间)不换行,表示目标状态。
输出格式
Line 1: 包括一个整数,表示最短操作序列的长度。
Line 2: 在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出60个字符。
输入输出样例
样例输入1
2 6 8 4 5 7 3 1
样例输出1
7
BCABCCB
说明/提示
题目翻译来自NOCOW。
USACO Training Section 3.2
思路
广搜+map去重 可以先把它当字符串处理,再找出ABC三种操作的规律,用函数模拟。map里存操作序列。
Code
#include <bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
string en, c;
queue<pair<string, string> > q;
int dd[3][8] = {{7, 6, 5, 4, 3, 2, 1, 0}, {3, 0, 1, 2, 5, 6, 7, 4}, {0, 6, 1, 3, 4, 2, 5, 7}};
char tu[3] = {'A', 'B', 'C'};
map<string, int> mp;
string calc(string s, int id)
{
string ans = s;
fr(i, 0, 7)ans[i] = s[dd[id][i]];
return ans;
}
void bfs()
{
q.push(make_pair("12345678", ""));
string s, wy, ts, twy;
while (q.size())
{
s = q.front().first;
wy = q.front().second;
q.pop();
if (s == en)
{
cout << wy.size() << endl << wy;
break;
}
fr(i, 0, 2)
{
ts = calc(s, i);
if (mp.count(ts))
continue;
mp[ts] = 1;
twy = wy + tu[i];
q.push(make_pair(ts, twy));
}
}
}
int main()
{
fr(i, 1, 8)
{
cin >> c;
en += c;
}
bfs();
return 0;
}
#五一专属|向所有热爱分享的“技术劳动者”致敬#
最新文章
- C#中使用Socket实现简单Web服务器
- Switch能否用string做参数?
- Nodejs Express下引入本地文件的方法
- jenkins自动构建截图
- 使用CAShapeLayer与UIBezierPath画出想要的图形
- nmblookup
- 进程识别号(PID)的理解
- (转)IIS7 下部署Asp.net应用
- Spring对jdbc支持
- ES 集群调整、升级 最佳实践
- svg学习之旅(1)
- vue生命周期的介绍
- 一个故事讲明白线程的私家领地:ThreadLocal
- Ubuntu14.04 安装配置Opencv3.0和Python2.7
- python 多线程和多进程
- GIS小知识
- JDK学习AbstractQueuedSynchronizer和AbstractQueuedLongSynchronizer
- Nginx查看并发链接数
- 1034 Head of a Gang (30 分)
- CentOS7 yum方式安装 MongoDB 3.4 复制集
热门文章
- 附011.常见Linux镜像站点大全
- NFS学习笔记
- WSL与Windows环境共享
- Blazor和Vue对比学习(基础1.5):双向绑定
- EFCore常规操作生成的SQL语句一览
- 【数据库】MYSQL如何添加索引
- 无法启动报,To install it, you can run: npm install --save @/components/xxxx.vue
- 我熬夜读完这份“高分宝典”,竟4面拿下字节跳动offer
- Endeavour OS 安装流程中的一些小问题的对应的解决方案
- MVC - MVC的工作流程