Cube

发表于 | 分类于

题目

给你一个n×m的棋盘，有一个1×1×2的长方体竖直放在(1,1)上，你可以将其在棋盘上滚动，你的目标是让其竖直放在(n,m)上，问至少需要多少次操作。(放倒、竖直、翻滚)

INPUT

一行，两个整数n，m (n<=m)

OUTPUT

需要最少时间逃脱密室。若无解输出impossible。

SAMPLE

INPUT1

1 1

OUTPUT1

0

INPUT2

2 4

OUTPUT2

3

INPUT3

4 7

OUTPUT3

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int ans(0);
int main(){
    scanf("%d%d",&n,&m);
    if(n==1||n==2){
        if((m-1)%3){
            puts("impossible");
            return 0;
        }
        printf("%d",(((m-1)/3)<<1)+n-1);
        return 0;
    }
    if(n==3){
        if(m==3){
            puts("8");
            return 0;
        }
        ans=2;
        ans+=((m-1)/3)<<1;
        if((m-1)%3)
            ans+=2+(m-1)%3;
        printf("%d",ans);
        return 0;
    }
    ans+=((n-1)/3)<<1;//cout<<ans<<endl;
    ans+=(n-1)%3;//cout<<ans<<endl;
    ans+=((m-1)/3)<<1;//cout<<ans<<endl;
    ans+=(m-1)%3;//cout<<ans<<endl;
    printf("%d",ans);
}

我考试时竟然想了暴搜，我也是服我自己= =