slikar_checker.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <stdlib.h>

#define XX x,y,xm,ym, level+1

#define XY x,ym,xm,yy, level+1

#define YX xm,y,xx,ym, level+1

#define YY xm,ym,xx,yy, level+1

#define PERM(a,b,c,d) a(XX)&&b(XY)&&c(YX)&&d(YY)

#define TRACE(a,b,c,d) a(XX,true)+b(XY,true)+c(YX,true)+d(YY,true)

#define CURRENT x][y][level

int min(int a, int b){ return a>b?b:a; }

int min(int a, int b, int c){ return a>b?(b>c?c:b):(a>c?c:a); }

int n;

char a[567][567];

char b[567][567];

char T[567][567];

int F[567][567][11];

int G[567][567][11];

int H[567][567][11];

int FF[567][567][11];

int GG[567][567][11];

int HH[567][567][11];

bool g(int x, int y, int xx, int yy, int level){

    if (xx-x==1 && yy-y==1) return a[xx][yy]!='1';

    if (GG[CURRENT]++) return G[CURRENT];

    int xm=(x+xx)/2;

    int ym=(y+yy)/2;

    return G[CURRENT]=PERM(g,g,g,g);

}

bool h(int x, int y, int xx, int yy, int level){

    if (xx-x==1 && yy-y==1) return a[xx][yy]!='0';

    if (HH[CURRENT]++) return H[CURRENT];

    int xm=(x+xx)/2;

    int ym=(y+yy)/2;

    return H[CURRENT]=PERM(h,h,h,h);

}

bool f(int x, int y, int xx, int yy, int level){

    if (xx-x==1 && yy-y==1) return true;

    if (FF[CURRENT]) return F[CURRENT];

    int xm=(x+xx)/2;

    int ym=(y+yy)/2;

    int rA1,rA2,rA3,rA4,rA5,rA6;

    int rB1,rB2,rB3,rB4,rB5,rB6;

    rA1 = PERM(f,f,g,h);

    rA2 = PERM(f,g,f,h);

    rA3 = PERM(f,g,h,f);

    rA4 = PERM(g,f,f,h);

    rA5 = PERM(g,f,h,f);

    rA6 = PERM(g,h,f,f);

    int rA = rA1||rA2||rA3||rA4||rA5||rA6;

    rB1 = PERM(f,f,h,g);

    rB2 = PERM(f,h,f,g);

    rB3 = PERM(f,h,g,f);

    rB4 = PERM(h,f,f,g);

    rB5 = PERM(h,f,g,f);

    rB6 = PERM(h,g,f,f);

    int rB = rB1||rB2||rB3||rB4||rB5||rB6;

    FF[CURRENT]=true;

    F[CURRENT]=rA||rB;

    return rA||rB;

}

main(int argc, char ** argv){

    int i, X, j;

    if (argc > 1) freopen(argv[1], "r", stdin);

    scanf("%d", &n);

    for (i=1; i<=n; i++)

    scanf("%s", b[i]+1);

    if (argc > 1) freopen(argv[2], "r", stdin);

    scanf("%d", &X);

    for (i=1; i<=n; i++)

    scanf("%s", a[i]+1);

    for (i=1; i<=n; i++)

    for (j=1; j<=n; j++)

    if (a[i][j] != b[i][j]) printf("X");

    printf(" %d\n", X);

    for (i=1; i<=n; i++)

    for (j=1; j<=n; j++)

    if (a[i][j]!='0' && a[i][j]!='1') printf("Invalid\n");

    printf("%d\n", f(0,0,n,n,1));

}

Nhận xét