# 13689 - Doracarpet

>author: Utin
###### tags: `recursion`

---

## Brief
See the code below

## Solution 0

#include <stdio.h>

char table[5][5];
char ans[10001][10001];

void initialize(); //初始化1的情況並存在table
void f0(int size, int index_i, int index_j, int range); //若size是偶數
void f1(int size, int index_i, int index_j, int range); //若size是奇數
int power(int a); //2的a次方
void k0(int range, int index_i, int index_j); //全空
void k1(int range, int index_i, int index_j); //缺右上
void k2(int range, int index_i, int index_j); //缺左上
void k3(int range, int index_i, int index_j); //缺左下
void k4(int range, int index_i, int index_j); //缺右下

int main() {
    initialize();

    int n;
    scanf("%d", &n);

    int range = power(n+1); //range為圖的寬度
    if (n%2 == 0) f0(n, 0, 0, range);
    else f1(n, 0, 0, range);
    //輸出
    for (int i=0; i<range; i++) {
        for (int j=0; j<range; j++) {
            printf("%c", ans[i][j]);
        }
        printf("\n");
    }
}

void initialize() {
    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            if ((i == 0 || i == 3) && (j == 0 || j == 3)) table[i][j] = '.';
            else table[i][j] = '#';
        }
    }
}

void f0(int size, int index_i, int index_j, int range) {
    f1(size-1, index_i, index_j, range/2);

    for (int i=index_i; i<index_i+range/2; i++) {
        for (int j=index_j; j<index_j+range/2; j++) {
            ans[i+range/2][j] = ans[i][j];
            ans[i][j+range/2] = ans[i][j];
            ans[i+range/2][j+range/2] = ans[i][j];
        }
    }
}

void f1(int size, int index_i, int index_j, int range) {
    if (size == 1) {
        for (int i=index_i; i<index_i+4; i++) {
            for (int j=index_j; j<index_j+4; j++) {
                ans[i][j] = table[i-index_i][j-index_j];
            }
        }
    }
    else {
        f0(size-1, index_i+range/4, index_j+range/4, range/2);

        k0(range/4, index_i, index_j);
        k1(range/4, index_i, index_j+range/4);
        k2(range/4, index_i, index_j+2*range/4);
        k0(range/4, index_i, index_j+3*range/4);
        k3(range/4, index_i+range/4, index_j);
        k4(range/4, index_i+range/4, index_j+3*range/4);
        k2(range/4, index_i+2*range/4, index_j);
        k1(range/4, index_i+2*range/4, index_j+3*range/4);
        k0(range/4, index_i+3*range/4, index_j);
        k4(range/4, index_i+3*range/4, index_j+range/4);
        k3(range/4, index_i+3*range/4, index_j+2*range/4);
        k0(range/4, index_i+3*range/4, index_j+3*range/4);
    }
}

int power(int a) {
    if(a > 0) return 2 * power(a-1);
    else return 1;
}

void k0(int range, int index_i, int index_j) {
    for(int i = index_i; i < index_i + range; i++) {
        for(int j = index_j; j < index_j + range; j++) {
            ans[i][j] = '.';
        }
    }
}

void k1(int range, int index_i, int index_j) {
    for(int i = index_i; i < index_i + range; i++) {
        for(int j = index_j; j < index_j + range; j++) {
            if(i < index_i+range/2 && j >= index_j+range/2) ans[i][j] = '.';
            else ans[i][j] = '#';
        }
    }
}

void k2(int range, int index_i, int index_j) {
    for(int i=index_i; i<index_i+range; i++) {
        for(int j=index_j; j<index_j+range; j++) {
            if(i < index_i+range/2 && j < index_j+range/2) ans[i][j] = '.';
            else ans[i][j] = '#';
        }
    }
}

void k3(int range, int index_i, int index_j) {
    for(int i=index_i; i<index_i+range; i++) {
        for(int j=index_j; j<index_j+range; j++) {
            if(i >= index_i+range/2 && j < index_j+range/2) ans[i][j] = '.';
            else ans[i][j] = '#';
        }
    }
}

void k4(int range, int index_i, int index_j) {
    for(int i=index_i; i<index_i+range; i++) {
        for(int j=index_j; j<index_j+range; j++) {
            if(i >= index_i+range/2 && j >= index_j+range/2) ans[i][j] = '.';
            else ans[i][j] = '#';
        }
    }
}
// By Utin

## Reference