slikar.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 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];
int g(int x, int y, int xx, int yy, int level, bool tracing=false){
if (tracing)
for (int i=1; i+x<=xx; i++)
for (int j=1; j+x<=xx; j++)
T[x+i][y+j]='0';
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;
//printf("g(%d, %d, %d, %d, %d) = %d\n", x, y, xx, yy, level, PERM(g,g,g,g));
return G[CURRENT]=PERM(g,g,g,g);
}
int h(int x, int y, int xx, int yy, int level, bool tracing=false){
if (tracing)
for (int i=1; i+x<=xx; i++)
for (int j=1; j+x<=xx; j++)
T[x+i][y+j]='1';
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;
//printf("h(%d, %d, %d, %d, %d) = %d\n", x, y, xx, yy, level, PERM(h,h,h,h));
return H[CURRENT]=PERM(h,h,h,h);
}
int f(int x, int y, int xx, int yy, int level, bool tracing=false){
if (xx-x==1 && yy-y==1) {
if (tracing) T[xx][yy]=a[xx][yy];
return 0;
}
if (!tracing && 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 = min(min(rA1,rA2,rA3), min(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 = min(min(rB1,rB2,rB3), min(rB4,rB5,rB6));
int r=min(rA, rB);
//printf("f(%d, %d, %d, %d, %d) = %d\n", x, y, xx, yy, level, r);
if (tracing && r==rA){
if (r==rA1) TRACE(f,f,g,h);
else if (r==rA2) TRACE(f,g,f,h);
else if (r==rA3) TRACE(f,g,h,f);
else if (r==rA4) TRACE(g,f,f,h);
else if (r==rA5) TRACE(g,f,h,f);
else if (r==rA6) TRACE(g,h,f,f);
}
else if (tracing && r==rB){
if (r==rB1) TRACE(f,f,h,g);
else if (r==rB2) TRACE(f,h,f,g);
else if (r==rB3) TRACE(f,h,g,f);
else if (r==rB4) TRACE(h,f,f,g);
else if (r==rB5) TRACE(h,f,g,f);
else if (r==rB6) TRACE(h,g,f,f);
}
FF[CURRENT]=true;
F[CURRENT]=r;
return r;
}
main(){
int i;
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%s", a[i]+1);
printf("%d\n", f(0,0,n,n,1));
f(0,0,n,n,1,true);
for (i=1; i<=n; i++)
printf("%s\n", T[i]+1);
}
Nhận xét