Cube
题目
给你一个n×m的棋盘,有一个1×1×2的长方体竖直放在(1,1)上,你可以将其在棋盘上滚动,你的目标是让其竖直放在(n,m)上,问至少需要多少次操作。(放倒、竖直、翻滚)INPUT
一行,两个整数n,m (n<=m)OUTPUT
需要最少时间逃脱密室。若无解输出impossible。SAMPLE
INPUT1
1 1OUTPUT1
0INPUT2
2 4OUTPUT2
3INPUT3
4 7OUTPUT3
6
解题报告
看到“逃离密室”这四个字我是蒙的= =, (哪里提到密室了啊喂)
考试时就打了个n=1~3的特判,结果3还没打对= =
正解:
显然可以找规律。
n=1或2时,因为方块无法立起来在较小一维翻滚,所以只有1和2存在“impossible”情况,那么我们只需判断m与3的整除关系,显然只有(m-1)%3==0时才可能正好立起来到达终点,且步数为((m-1)/3)×2。如果n=2,还需加上方块横着滚一次的次数
n=3时最为特殊,因为方块可以通过各种奇怪的方法翻转,来达到立起来到达终点的结果,原因是因为n=3时,方块可以通过多次横滚加一次立起换向的方式达到效果,所以我们可以得到这样的式子:
ans=4+((m-1)/3)×2+(m-1)%3
然而我们需要注意3×3的情况,答案为8,我就不证了(不会证),其实自己画个图,翻两下就可以了
接下来是大部分的情况,我们考虑一个4×4的网格,显然,我们竖着操作两遍,横着操作两遍即可,那么就很简单了,假设我们加了一列,成了4×5,我们只需多横滚一次即可,所以很容易得出式子:
ans=((n-1)/3+(m-1)/3+(n-1)%3+(m-1)%3)×2
剩下的就是代码了
1 #include2 #include 3 #include 4 using namespace std; 5 int n,m; 6 int ans(0); 7 int main(){ 8 scanf("%d%d",&n,&m); 9 if(n==1||n==2){10 if((m-1)%3){11 puts("impossible");12 return 0;13 }14 printf("%d",(((m-1)/3)<<1)+n-1);15 return 0;16 }17 if(n==3){18 if(m==3){19 puts("8");20 return 0;21 }22 ans=2;23 ans+=((m-1)/3)<<1;24 if((m-1)%3)25 ans+=2+(m-1)%3;26 printf("%d",ans);27 return 0;28 }29 ans+=((n-1)/3)<<1;//cout< <
我考试时竟然想了暴搜,我也是服我自己= =