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