The 2013 ACM-ICPC Asia Changsha Regional Contest - K
Pocket Cube
Time Limit: 2 Seconds Memory Limit: 65536 KB
Pocket Cube is a 3-D combination puzzle. It is a 2 × 2 × 2 cube, which means it is constructed by 8 mini-cubes. For a combination of 2 × 2 mini-cubes which sharing a whole cube face, you can twist it 90 degrees in clockwise or counterclockwise direction, this twist operation is called one twist step.
Considering all faces of mini-cubes, there will be totally 24 faces painted in 6 different colors (Indexed from 0), and there will be exactly 4 faces painted in each kind of color. If 4 mini-cubes' faces of same color rely on same large cube face, we can call the large cube face as a completed face.
Now giving you an color arrangement of all 24 faces from a scrambled Pocket Cube, please tell us the maximum possible number of completed faces in no more than N twist steps.
Index of each face is shown as below:
Input
There will be several test cases. In each test case, there will be 2 lines. One integer N (1 ≤ N ≤ 7) in the first line, then 24 integers Ci seperated by a sinle space in the second line. For index 0 ≤ i < 24, Ci is color of the corresponding face. We guarantee that the color arrangement is a valid state which can be achieved by doing a finite number of twist steps from an initial cube whose all 6 large cube faces are completed faces.
Output
For each test case, please output the maximum number of completed faces during no more than N twist step(s).
Sample Input
1
0 0 0 0 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 5 5 5 5
1
0 4 0 4 1 1 2 5 3 3 1 1 2 5 3 3 4 0 4 0 5 2 5 2
Sample Output
6
2
一共是12种变化，但是有等价的，最后每一纬是2种变换，一共是6种变换。
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <set>
#define Max(a,b) ((a)>(b)?(a):(b))
#pragma comment(linker, "/STACK:16777216")
using namespace std ;
typedef long long LL ;
struct Cube{
int a[] ; void out(){
printf(" %d%d \n",a[],a[]) ;
printf(" %d%d \n",a[],a[]) ;
printf("%d%d%d%d%d%d\n",a[],a[],a[],a[],a[],a[]) ;
printf("%d%d%d%d%d%d\n",a[],a[],a[],a[],a[],a[]) ;
printf(" %d%d \n",a[],a[]) ;
printf(" %d%d \n",a[],a[]) ;
printf(" %d%d \n",a[],a[]) ;
printf(" %d%d \n",a[],a[]) ;
puts("") ;
} int complete_face(){
int sum = ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
if(a[]==a[]&&a[]==a[]&&a[]==a[])
sum++ ;
return sum ;
} Cube R_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
return o ;
} Cube R_count_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[]= a[];
o.a[]= a[];
o.a[]= a[];
o.a[]= a[] ;
o.a[]= a[] ;
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
return o ;
} Cube U_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
return o ;
} Cube U_count_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[]= a[];
o.a[]= a[];
o.a[]= a[];
o.a[]= a[] ;
o.a[]= a[] ;
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
return o ;
} Cube F_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
o.a[] = a[] ;
return o ;
} Cube F_count_colock(){
Cube o ;
for(int i = ;i < ;i++)
o.a[i] = a[i] ;
o.a[]= a[];
o.a[]= a[];
o.a[]= a[];
o.a[]= a[] ;
o.a[]= a[] ;
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
o.a[] =a[];
return o ;
} }; int N ;
int ans ; void dfs(Cube cb ,int step){
Cube o ;
if(step>N)
return ;
if(ans == )
return ; o = cb.F_colock() ;
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ; o = cb.F_count_colock() ;
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ; o = cb.R_colock() ;
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ; o = cb.R_count_colock() ;
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ; o = cb.U_colock();
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ; o = cb.U_count_colock() ;
ans = Max(ans,o.complete_face()) ;
dfs(o,step+) ;
} int main(){
Cube now ;
while(scanf("%d",&N)!=EOF){
for(int i = ;i < ;i++)
scanf("%d",&now.a[i]) ;
ans = now.complete_face() ;
dfs(now,) ;
printf("%d\n",ans) ;
}
return ;
}
最新文章
- 使用KRPano资源分析工具一键下载全景网站切片图
- 一款全兼容的播放器 videojs
- 李洪强iOS经典面试题128
- :root
- .net 页面跳转方式【转】
- 使用jni技术进行android应用签名信息核查及敏感信息保护
- C++习题 复数类--重载运算符+
- JSON.parse()和JSON.stringify()和eval('(' + result + ')')
- 基于Elastalert的安全告警剖析
- AVR 嵌入式单片机芯片的中断系统介绍
- python 饥饿的小易(网易笔试题)
- Swift 学习- 02 -- 基础部分2
- python 报错RuntimeError: dictionary changed size during iteration
- 简单易懂的博弈论讲解(巴什博弈、尼姆博弈、威佐夫博弈、斐波那契博弈、SG定理)
- 微擎开启性能优化里面的性能优化memcache内存优化及数据库读写分离
- C# 最大二叉堆算法
- javascript如何获取URL参数的值
- 使用Tensoflow实现梯度下降算法的一次线性拟合
- golang实现任务分发处理
- c++ 标准流文件
热门文章
- HBase(二): c#访问HBase之股票行情Demo
- [hadoop] hadoop “util.NativeCodeLoader: Unable to load native-hadoop library for your platform”
- 多线程操作（ThreadPool.QueueUserWorkItem
- 03 在Linux下安装Myeclipse及Tomcat（含下载）
- Python装饰器通用样式
- Zabbix agent on Microsoft Windows
- [vim]VIM快捷键整理
- SVN 分支及合并的介绍和实践---命令行
- Qt属性表控件的使用 QtTreePropertyBrowser
- DBA_Oracle Erp升级时如何确定具体的Patch ID（案例）