BruceJay's Blog

ZJOI2005 梦幻折纸

| Comments

To start with

这题OJ上找不到??

Bruce实力裁纸折,然后,就没有然后了。

Problem

给一个N*M的格子,每个格子都写有一个1~N*M的数字。然后将这张格子折叠成1*1,使得第1层标号为1,使得第2层标号为2...,第i层标号为i...。
给几个良心样例:
1 7
3 1 7 6 5 4 2
AllRight
2 2
1 2
3 4
Cheat
2 3
2 1 6
3 4 5
Allright
4 4
11 12 15 14
10 9 16 13
5 8 1 2
6 7 4 3
Cheat
样例解释就不给了。

Solution

折成后,按原格子中所有的边(两个1*1格子间的分界线)折叠后开口的方向分为四类。
拿第四个样例说:
11-12,15-14,10-9...,4-3开口方向相同。
12-15,9-16,8-1,7-4开口方向相同。
11-10,12-9,15-16,...,2-3开口方向相同。
10-5,9-8,16-1,13-2开口方向相同。
对于开口方向相同的一类边,如果两条边有交叉(1-3,2-4之类的),那么就不可能折成。
交叉用栈来判断。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
const int Size = 10100;
int a[N][N]; int f[Size];
int Stack[Size];
int T,n,m,top; bool ans;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

bool Check()
{
    top=0;
    for(int i=1;i<=n*m;i++){
        if(!f[i]) Stack[++top]=i;
        else if(f[i]>0){
            if(Stack[top]!=f[i]) return false;
            else top--;
        }
    }
    return true;
}

int main()
{
    freopen("foldgirl.in","r",stdin);
    freopen("foldgirl.out","w",stdout);
    T=read();
    while(T--){
        n=read(); m=read(); ans=true;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read();
        memset(f,-1,sizeof(f));
        for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j+=2){
            int u=a[i][j],v=a[i][j-1];
            if(u>v) swap(u,v);
            f[u]=0; f[v]=u;
        }
        ans&=Check();
        memset(f,-1,sizeof(f));
        for(int i=1;i<=n;i++)
        for(int j=3;j<=m;j+=2){
            int u=a[i][j],v=a[i][j-1];
            if(u>v) swap(u,v);
            f[u]=0; f[v]=u;
        }
        ans&=Check();
        memset(f,-1,sizeof(f));
        for(int i=2;i<=n;i+=2)
        for(int j=1;j<=m;j++){
            int u=a[i][j],v=a[i-1][j];
            if(u>v) swap(u,v);
            f[u]=0; f[v]=u;
        }
        ans&=Check();
        memset(f,-1,sizeof(f));
        for(int i=3;i<=n;i+=2)
        for(int j=1;j<=m;j++){
            int u=a[i][j],v=a[i-1][j];
            if(u>v) swap(u,v);
            f[u]=0; f[v]=u;
        }
        ans&=Check();
        if(ans) puts("AllRight");
        else puts("Cheat");
    }
    return 0;
}

Last but not least

还是要多动手。这么蠢的Bruce都做出来了。

Comments

comments powered by Disqus