hdu 5012 Dice
2024-10-19 00:22:02
Problem Description
There are 2 special dices on the table. On each face of the dice, a distinct number was written. Consider a1.a2,a3,a4,a5,a6 to be numbers written on top face, bottom face, left face, right face, front face and back face of dice A. Similarly, consider b1.b2,b3,b4,b5,b6 to be numbers on specific faces of dice B. It’s guaranteed that all numbers written on dices are integers no smaller than 1 and no more than 6 while ai ≠ aj and bi ≠ bj for all i ≠ j. Specially, sum of numbers on opposite faces may not be 7.
At the beginning, the two dices may face different(which means there exist some i, ai ≠ bi). Ddy wants to make the two dices look the same from all directions(which means for all i, ai = bi) only by the following four rotation operations.(Please read the picture for more information)Now Ddy wants to calculate the minimal steps that he has to take to achieve his goal.
At the beginning, the two dices may face different(which means there exist some i, ai ≠ bi). Ddy wants to make the two dices look the same from all directions(which means for all i, ai = bi) only by the following four rotation operations.(Please read the picture for more information)Now Ddy wants to calculate the minimal steps that he has to take to achieve his goal.
Input
There are multiple test cases. Please process till EOF.
For each case, the first line consists of six integers a1,a2,a3,a4,a5,a6, representing the numbers on dice A.
The second line consists of six integers b1,b2,b3,b4,b5,b6, representing the numbers on dice B.
For each case, the first line consists of six integers a1,a2,a3,a4,a5,a6, representing the numbers on dice A.
The second line consists of six integers b1,b2,b3,b4,b5,b6, representing the numbers on dice B.
Output
For each test case, print a line with a number representing the answer. If there’s no way to make two dices exactly the same, output -1.
Sample Input
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 5 6 4 3
1 2 3 4 5 6
1 4 2 5 3 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 5 6 4 3
1 2 3 4 5 6
1 4 2 5 3 6
Sample Output
0
3
-1
3
-1
Source
题意:两个骰子,要把第一个骰子转到和第二个一样,有4种转法,求最少的次数
直接bfs,不过我用G++提交超时,用C++提交可以过,可能是使用了queue的原因。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
struct Node
{
int a[];
int t;
}st,ed;
int vis[][][][][][];
void bfs()
{ queue<Node>q;
q.push(st); vis[st.a[]][st.a[]][st.a[]][st.a[]][st.a[]][st.a[]]=;
Node t1,t2;
Node tmp;
while(!q.empty())
{
t1=q.front();
q.pop();
if(t1.a[]==ed.a[] && t1.a[]==ed.a[]&& t1.a[]==ed.a[]&& t1.a[]==ed.a[]&& t1.a[]==ed.a[] && t1.a[]==ed.a[])
{
printf("%d\n",t1.t);
return;
} t2=t1;
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
if(vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]==)
{
vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]=;
t2.t=t1.t+;
q.push(t2);
} t2=t1;
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
if(vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]==)
{
vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]=;
t2.t=t1.t+;
q.push(t2);
} t2=t1;
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
if(vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]==)
{
vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]=;
t2.t=t1.t+;
q.push(t2);
} t2=t1;
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
t2.a[]=t1.a[];
if(vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]==)
{
vis[t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]][t2.a[]]=;
t2.t=t1.t+;
q.push(t2);
}
}
printf("-1\n");
}
int main()
{
while(scanf("%d%d%d%d%d%d",&st.a[],&st.a[],&st.a[],&st.a[],&st.a[],&st.a[])==)
{
scanf("%d%d%d%d%d%d",&ed.a[],&ed.a[],&ed.a[],&ed.a[],&ed.a[],&ed.a[]);
st.t=;
memset(vis,,sizeof(vis));
bfs();
}
return ;
}
最新文章
- 用命令行工具创建 NuGet 程序包
- CSharpGL(30)用条件渲染(Conditional Rendering)来提升OpenGL的渲染效率
- 我厂 WiFi SDK 开源了, 直接开源 WiFi 万能钥匙核心功能,造福中小开发者
- Windows下几款免费C/C++开发工具简介
- 关于js异步上传文件
- IOS中把字符串加密/IOS中怎么样MD5加密/IOS中NSString分类的实现
- 最新微信小程序(应用号)视频教程,实战教程
- SCTP 关联的建立和终止
- C# 十进制和十六进制转换
- php 常用代码段
- xshell设置界面的编码方式
- python 3.6 +pyMysql 操作mysql数据库
- Hbase记录-zookeeper部署
- 数组的高级API-sort
- 英语初级学习系列-00-Name-介绍自己
- Python3.5 学习二十二
- Flutter开发中的几个常用函数
- 1086. Tree Traversals Again (25)-树的遍历
- Android Activity启动流程源码全解析(2)
- <;漫步华尔街——股市历久弥新的成功投资策略>;读书笔记