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