P2730 [USACO3.2] 魔板 Magic Squares

2024-08-25 12:12

本文主要是介绍P2730 [USACO3.2] 魔板 Magic Squares,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[USACO3.2] 魔板 Magic Squares

题目背景

在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有 8 8 8 个大小相同的格子的魔板:

1 2 3 4 1\quad2\quad3\quad4 1234

8 7 6 5 8\quad7\quad6\quad5 8765

题目描述

我们知道魔板的每一个方格都有一种颜色。这 8 8 8 种颜色用前 8 8 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于上图的魔板状态,我们用序列 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } \{1,2,3,4,5,6,7,8\} {1,2,3,4,5,6,7,8} 来表示。这是基本状态。

这里提供三种基本操作,分别用大写字母 A \text A A B \text B B C \text C C 来表示(可以通过这些操作改变魔板的状态):

A \text A A:交换上下两行;

B \text B B:将最右边的一列插入最左边;

C \text C C:魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范:

A \text A A

8 7 6 5 8\quad7\quad6\quad5 8765

1 2 3 4 1\quad2\quad3\quad4 1234

B \text B B

4 1 2 3 4\quad1\quad2\quad3 4123

5 8 7 6 5\quad8\quad7\quad6 5876

C \text C C

1 7 2 4 1\quad7\quad2\quad4 1724

8 6 3 5 8\quad6\quad3\quad5 8635

对于每种可能的状态,这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换,输出基本操作序列。

输入格式

只有一行,包括 8 8 8 个整数 a 1 , a 2 ⋯ a 8 ( 1 ≤ a 1 , a 2 ⋯ a 8 ≤ 8 ) a_1,a_2\cdots a_8(1\leq a_1,a_2\cdots a_8\leq8) a1,a2a8(1a1,a2a88),用空格分开,不换行,表示目标状态。

输出格式

第一行包括一个整数,表示最短操作序列的长度。

第二行在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出 60 60 60 个字符。

样例 #1

样例输入 #1

2 6 8 4 5 7 3 1

样例输出 #1

7 
BCABCCB

提示

题目翻译来自 NOCOW。

USACO Training Section 3.2

code:

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
int g[2][4];
unordered_map<string ,int >dist;//存到当前状态需要几步
unordered_map<string,pair<char ,string > >pre;//存从哪一个状态转移过来的,而且要存A还是B还是C操作(char是存ABC,pair中的string是存从哪一个状态转移过来的)pre[s]={‘A或B或C’,t};
queue<string>q;
void set1(string s){//把字符串转化为2*4的矩阵,并且要顺时针存储for(int i=0;i<4;i++){g[0][i]=s[i];}for(int i=3,j=4;i>=0;i--,j++){g[1][i]=s[j];}
}
string get1(){//把2*4的矩阵转化为字符串string res;for(int i=0;i<4;i++){res+=g[0][i];//字符串加减就是字符串的拼接}for(int i=3;i>=0;i--){res+=g[1][i];}return res;
}
string move0(string s){//进行Aset1(s);for(int i=0;i<4;i++){swap(g[0][i],g[1][i]);}return get1();
}
string move1(string s){//进行Bset1(s);char v0=g[0][3],v1=g[1][3];//把最后一列数存起来,然后把其他位置都往后移动一位for(int i=3;i>0;i--){for(int j=0;j<2;j++){g[j][i]=g[j][i-1];}}g[0][0]=v0;g[1][0]=v1;return get1();
}
string move2(string s){//进行Cset1(s);//先把左上角的数存起来,然后直接转一圈,类似于冒泡char tmp=g[0][1];g[0][1]=g[1][1];g[1][1]=g[1][2];g[1][2]=g[0][2];g[0][2]=tmp;return get1();
}
int bfs(string start,string end1){q.push(start);dist[start]=0;while(q.size()){auto t=q.front();q.pop();if(t==end1){return dist[end1];}string m[3];m[0]=move0(t);m[1]=move1(t);m[2]=move2(t);for(int i=0;i<3;i++){string s=m[i];if(!dist.count(s)){//如果s状态没有被访问过则可以去访问dist[s]=dist[t]+1;pre[s]={char(i+'A'),t};//i+'A'可以把0,1,2···,转化为A,B,C,s表示下一个状态if(s==end1){return dist[end1];}q.push(s);}}}return -1;
}
int main(){int x;string start,end1;for(int i=1;i<=8;i++){cin>>x;end1+=char(x+'0');//数字变字符,+'0'}for(int i=1;i<=8;i++){start+=char(i+'0');}int res=bfs(start,end1);cout<<res<<endl;string res2;while(end1!=start){//从目标状态往起始状态开始存储,所以最终答案需要翻转res2+=pre[end1].first;//字符串的拼接end1=pre[end1].second;}reverse(res2.begin(),res2.end());//翻转最终答案if(res2.size()){cout<<res2<<endl;}return 0;
}

这篇关于P2730 [USACO3.2] 魔板 Magic Squares的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1105524

相关文章

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

Qlik数据集成 | Qlik 连续 14 年稳居 2024 Gartner® ABI Magic Quadrant™ 领导者

Qlik 再次当选 2024 年 Gartner® 分析和商业智能平台 Magic Quadrant™ 领导者! 近日,作为引领当今数据集成、数据质量和分析解决方案市场的行业领导者, Qlik 再次当选 2024 年 Gartner® 分析和商业智能平台 Magic Quadrant™ 领导者! 得益于 Qlik 在愿景完备性和执行能力方面的出色表现,这已经是 Qlik 第 14 年位居领导者象

Magic推出100M个token的上下文

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领域的领跑者。点击订阅,与未来同行! 订阅:https://rengongzhineng.io/ 目前,AI模型有两种学习方式:一种是通过训练,另一种是在推理过程中通

CodeForces 425D Sereja and Squares

题意: 平面上有n个点  问  最多能组成多少个边与坐标轴平行的正方形 思路: 这是一个通过不断二分查找乱搞的题… 首先枚举左下角  然后分别往上往右找左上角和右下角 这时如果发现边长不想等就通过长边长度在短边的方向二分查找最接近的值  不停往上往右延伸 如果发现边长想等了  那么要判断一下对应的左上角坐标出是不是有一个点 怎么判断呢  通过将所有点hash出一个值  然后二分

【二分查找】-POJ-2002-Squares

题目链接:http://poj.org/problem?id=2002 题目描述:给出平面上若干个点,问能最多构成几个不重复的正方形。 解题思路: 第一反应是标记数组直接搜,好吧,内存超限。然后想了BFS或者DFS,太没前途了。然后想了哈希,不失为一种方法,但是不会操作。好吧还是按照九野大神选题的初衷来做吧——二分查找,为了锻炼自己,嗯!手写!好吧,我写的只是二分找 x 坐标,y 坐标没二分

SDUT2880 Devour Magic 线段树(set+add标记)

Devour Magic Time Limit: 2000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 In Warcraft III, Destroyer is a large flying unit that must consume magic to sustain its mana. Breaking fre

HDU1153——Magic Bitstrings,HDU1171——Big Event in HDU,HDU1261——字串数

HDU1153——Magic Bitstrings 题目描述 问题 - 1153 (hdu.edu.cn) 运行代码 #include <iostream>#include <vector>int main() {long long p;while (std::cin >> p) {if (p == 0) break;if (p == 2) {std::cout << "Imposs

MemSQL Start[c]UP 2.0 - Round 1 C. Magic Trick

Codeforces MemSQL Start[c]UP 2.0 - Round 1 C. Magic Trick 首先,我们先假设有抽出的牌样式为A 则,抽到同样的牌(不是同样类型)的概率为 1 / N 则,抽到不同的牌的概率为 N-1 / N 此时抽到A类型的概率为,在原来的N*M张中去掉我们最先抽出的一张A,再从中抽出剩下的 M-1张A类牌 综上所述,答案为 1 / N + (

Phpstorm Invalid MIT-MAGIC-COOKIE-1 key

problem: Invalid MIT-MAGIC-COOKIE-1 key resolved: cd /rootln -s /home/username/.Xauthority

新手搭建Magic-API

项目场景: 我本是一个前端和GIS开发工程师,但新单位并没有配置完整的开发团队,确切说目前只有我一个人做开发,那么肯定避免不了要研究下后端。最近有一个小程序要开发,管理平台我直接用的fastAdmin+thinkphp写完了页面和接口。秉着持续学习的精神,小程序的接口我想试着用java写。但是我从来没有写过一行java代码,经过一系列的考察,我选择了Magic-api这个低代码开发工具来写我的首