求调

P1228 地毯填补问题

lby_commandBlock @ 2024-10-17 22:37:56

#include <bits/stdc++.h>
#include <windows.h>
#define endl '\n'
using namespace std;

const int N = (1 << 10) + 9;

struct out {
    int x, y, c;
};

vector<out> vec;

int n, x, y;

bool f[N][N];

void Pause() {
    system("pause");
}

void dfs(int x1, int y1, int x2, int y2) {
    printf("------------------------------------\n%d %d %d %d\n", x1, y1, x2, y2);
    system("cls");
    for (int i = 1; i <= (1 << n); i++) {
        for (int j = 1; j <= (1 << n); j++)
            cout << (f[i][j] ? '*' : '.');
        cout << endl;
    }
    Pause();
    if ((y2 - y1) * (x2 - x1) == 4) {
        printf("RUNNING!\n");
        for (int i = x1; i < x2; i++) {
            for (int j = y1; j < y2; j++) {
                if (f[i + 1][j + 1]) {
                    printf("FIND!\n");
                    if (i == x1 && j == y1) {
                        printf("%d %d 1\n", x2, y2);
                    } else if (i == x1 && j == y1 + 1) {
                        printf("%d %d 2\n", x1 + 2, y1 + 1);
                    } else if (i == x1 + 1 && j == y1) {
                        printf("%d %d 3\n", x1 + 1, y2);
                    } else if (i == x1 + 1 && j == y1 + 1) {
                        printf("%d %d 4\n", x1 + 1, y1 + 1);
                    }
                    f[x1 + 1][y1 + 1] = true;
                    f[x1 + 1][y2] = true;
                    f[x2][y1 + 1] = true;
                    f[x2][y2] = true;
                    return;
                }
            }
        }
    }
    int cx = (x1 + x2) >> 1;
    int cy = (y1 + y2) >> 1;
    int x, y;
    for (int i = x1 + 1; i <= x2; i++) {
        for (int j = y1 + 1; j <= y2; j++) {
            if (f[i][j]) {
                x = i;
                y = j;
                printf("I FIND! x:%d,y:%d;(x1,x2):(%d,%d);(y1,y2):(%d,%d)\n", x, y, x1, x2, y1, y2);
                Pause();
                break;

            }
        }
    }
    int fx = 0;
    if (x < cx && y < cy)
        fx = 1; //左上
    if (x < cx && y >= cy)
        fx = 2; //右上
    if (x >= cx && y < cy)
        fx = 3; //左下
    if (x >= cx && y >= cy)
        fx = 4; //右下
    if (fx == 1) {
        f[cx + 1][cy + 1] = true;
        f[cx + 1][cy] = true;
        f[cx][cy + 1] = true;
        printf("%d %d 1\n", cx + 1, cy + 1);
    } else if (fx == 2) {
        f[cx + 1][cy + 1] = true;
        f[cx + 1][cy] = true;
        f[cx][cy] = true;
        printf("%d %d 2\n", cx + 1, cy);
    } else if (fx == 3) {
        f[cx + 1][cy + 1] = true;
        f[cx][cy] = true;
        f[cx][cy + 1] = true;
        printf("%d %d 3\n", cx, cy + 1);
    } else {
        f[cx][cy] = true;
        f[cx + 1][cy] = true;
        f[cx][cy + 1] = true;
        printf("%d %d 4\n", cx, cy);
    }
    printf("更深——————\n");
    Pause();
    dfs(x1, y1, cx, cy);
    dfs(x1, cy, cx, y2);
    dfs(cx, y1, x2, cy);
    dfs(cx, cy, x2, y2);
    printf("回来——————\n");
    Pause();
}

int main() {
    cin >> n >> x >> y;
    f[x][y] = true;
    dfs(0, 0, 1 << n, 1 << n);
    return 0;
}

54分,已加调试信息


|