[hash-bfs]USACO 3.2 Magic Squares 魔板

news/2024/2/20 18:25:34

魔 板 魔板


题目描述

在成功地发明了魔方之后,拉比克先生发明了它的二维版本,称作魔板。这是一张有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个字符。


样例输入

2 6 8 4 5 7 3 1


样例输出

7
BCABCCB


解析

BFS加上hash表


Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx=100003;
const int rule[3][8]={{8,7,6,5,4,3,2,1},{4,1,2,3,6,7,8,5},{1,7,2,4,5,3,6,8}};
int fa[maxx],num[maxx],xx,h,t;
string st[maxx],ss,hs[maxx];
char q[maxx]; 
bool hash(string s){int ans=0;for(int i=0;i<8;i++){ans=(ans*8)+(ans*2)+s[i]-48;}int i=0;ans%=maxx;while(i<maxx&&hs[(i+ans)%maxx]!=""&&hs[(i+ans)%maxx]!=s){i++;}if(hs[(i+ans)%maxx]==""){hs[(i+ans)%maxx]=s;return false;}else return true;
}
void bfs(){hash("12345678");st[1]="12345678";h=0;t=1;while(h<t){h++;for(int i=0;i<3;i++){t++;fa[t]=h;st[t]="";num[t]=num[h]+1;if(i==0) q[t]='A';else if(i==1) q[t]='B';else if(i==2) q[t]='C';for(int j=0;j<8;j++){st[t]+=st[h][rule[i][j]-1];}if(hash(st[t])) t--;else if(st[t]==ss) return; }}
}
void write(int x){if(x==1) return;write(fa[x]);printf("%c",q[x]);
}
int main(){for(int i=0;i<=7;i++){scanf("%d",&xx);ss+=xx+48;}if(ss=="12345678") printf("0");else{bfs();printf("%d\n",num[t]);write(t);}return 0;
}

http://www.ppmy.cn/news/628815.html

相关文章

洛谷_P3808

题目链接 点此跳转 代码 #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <iostream> #include <sstream> #include <algorithm> #include <cmath> #include <vector> #includ…

洛谷 P2888 [USACO07NOV] 牛栏Cow Hurdles

题目描述 Farmer John wants the cows to prepare for the county jumping competition, so Bessie and the gang are practicing jumping over hurdles. They are getting tired, though, so they want to be able to use as little energy as possible to jump over the hurd…

08-Buffer

Buffer初识 在引入 TypedArray 之前&#xff0c;JavaScript 语言没有用于读取或操作二进制数据流的机制。 Buffer 类是作为 Node.js API 的一部分引入的&#xff0c;用于在 TCP 流、文件系统操作、以及其他上下文中与八位字节流进行交互。这是来自 Node.js 官网的一段描述&…

Codeforces Round#707 B-Napoleon Cake

题目传送门 题目大意 有n层蛋糕每个第i层上要涂上一层单位面积为ai的奶油&#xff0c;奶油会顺着蛋糕侧边流下&#xff0c;每ai面积的奶油就可以覆盖ai层蛋糕&#xff0c;你最后需要输出哪些层有奶油覆盖哪些层没有。 输入格式 第一行输入t(1<t<20000),表示t组测试样例…

洛谷 P2676 [USACO07DEC]Bookshelf B

接下来我们继续看排序题单的下一道—— P2676 [USACO07DEC]Bookshelf B&#x1f447; 题目描述 这道题目也是一样的&#xff0c;我们要透过题目所给的生活情境&#xff0c;直接看到它的本质所在——给定一个长度为N的正整数数列&#xff0c;里面的数字为乱序排列&#xff0c;问…

洛谷P4089The Bovine Shuffle S 详解

# [USACO17DEC]The Bovine Shuffle S ## 题面翻译 背景 FJ 坚信快乐的牛可以产出更多的牛奶&#xff0c;因此 FJ 在牛棚里安装了一个巨大的迪斯科球并且打算让奶牛们学会跳舞。 FJ在许多出名的奶牛舞中选择了一种叫做 Bovine Shuffle 的舞蹈。这种舞蹈由 FJ 的 $N$ 头奶牛组…

P1884 [USACO12FEB]Overplanting S——洛谷

解题思路&#xff1a; 离散化 差分矩阵 解题步骤&#xff1a; 因为原始坐标系与差分的坐标系不同&#xff0c;所以要进行坐标系的变换 离散化处理缩小查找空间 图中坐标离散化后&#xff0c;再转化为格子的坐标&#xff0c;因为之前存贮的坐标是点的坐标&#xff0c;每个格…

dfs-1756:八皇后及1700:八皇后问题

总时间限制: 1000ms 内存限制: 65536kB 描述 会下国际象棋的人都很清楚&#xff1a;皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上&#xff08;有8 * 8个方格&#xff09;&#xff0c;使它们谁也不能被吃掉&#xff01;这就是著名的八皇后问题…

uva705 - Slash Maze 【转化+dfs】

题目&#xff1a;uva705 - Slash Maze 题意&#xff1a;给出一个迷宫&#xff0c;看题目给出的图就知道&#xff0c;由 \ 和 / 组成&#xff0c;让你求有几个环&#xff0c;然后最大的环由几个矩形组成。 分析&#xff1a;这是一道很灵活的题目&#xff0c;关键在于对题目给出…

洛谷 P2895 [USACO08FEB]Meteor Shower S(BFS与时间)

题目 https://www.luogu.com.cn/problem/P2895#submit 思路 有一些问题与时间有关&#xff0c;往往题目描述是&#xff1a;每隔一段时间&#xff0c;一些点就被摧毁而不能走了&#xff0c;问能够到达指定点或者到达指定点的时间&#xff1f; 这类问题可以使用BFS求解&#xf…

洛谷CF1551B

#include<stdlib.h> #include<stdio.h> using namespace std; int t; char data[55]; int flag[26];//标记所有字母是否出现过 int num1; int num2; int num; int main() { scanf("%d",&t); char temp; scanf("\n"); for(…

洛谷P2888 [USACO07NOV]Cow Hurdles S 题解

洛谷P2888 [USACO07NOV]Cow Hurdles S 题解 题目链接&#xff1a;P2888 [USACO07NOV]Cow Hurdles S 题意&#xff1a;Farmer John 想让她的奶牛准备郡级跳跃比赛&#xff0c;贝茜和她的伙伴们正在练习跨栏。她们很累&#xff0c;所以她们想消耗最少的能量来跨栏。 显然&#x…

洛谷P2768

二分真的好难/(ㄒoㄒ)/~~&#xff01; 首先看题&#xff0c;题目中我们可以知道选手跳跃最短距离的最大值&#xff0c;所以我们可以使用二分。 判断是否需要二分可以看题目中是否有类似求最短距离的最大值或者最大距离的最小值。 那么本题怎么进行二分呢 我们可以以整段距离…

Buffalo框架的使用

【整体介绍&#xff0c;建议先看完下面的内容在回过来看这个介绍】当用户输入账号密码后&#xff0c;点击“提交”按钮&#xff0c;则执行JSh中的getInfo()方法&#xff0c;该方法会调用Buffalo框架中的remoteCall("UserService.getInfo",[username,password],functi…

洛谷 AT_abc178_b [ABC178B] Product Max

洛谷 AT_abc178_b [ABC178B] Product Max 1、题目题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示制約Sample Explanation 1Sample Explanation 2 2、翻译题面&#xff1a; AC代码&#xff…

洛谷P1077摆花

文章目录 一、题目描述二、思路三、代码 一、题目描述 https://www.luogu.com.cn/problem/P1077 题目描述很容易看懂 二、思路 动态规划题目&#xff0c;首先定义状态 dp[i][j]:摆前i种花&#xff0c;一共摆j盆的方案数。 i&#xff1a;1~n j&#xff1a;1~m 需要注意的时&a…

IP地点定位为什么有误差?

随着互联网的不断普及&#xff0c;人们对IP地点定位需求越来越多。然而&#xff0c;即便是在现代技术的支持下IP地点定位仍然存在误差。那么&#xff0c;IP地点定位为什么会出现误差呢&#xff1f; IP&#xff08;Internet Protocol&#xff09;地址是指互联网协议&#xff08;…

数据库技术之MySQL高级

目录 子查询与表连接 子查询(嵌套sql) 利⽤⼦查询进⾏过滤 作为计算字段使⽤⼦查询 外键 表关系 关系表 表联结 联结多个表 使⽤表别名 AS 组合查询 UNION 总结&#xff1a;表联结 练习题 sql_mode sql_mode值的含义 MySQL事务 概述 ⼀,事务的语法 ⼆,事务的…

一篇博客帮你了解MySQL高级知识

MySQL高级 一、子查询与表连接子查询&#xff08;嵌套SQL&#xff09;关系表组合查询 UNION 二、MySQL事务概述事务的语法事务的ACID特性事物的并发问题事物的的隔离级别不同隔离级别的锁的情况&#xff08;了解&#xff09;隐式提交&#xff08;了解&#xff09; 三、MySQL中的…

构建高并发平台架构

一、 设计理念 1. 空间换时间 1) 多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量)&#xf…
最新文章