没开数组mle

P1228 地毯填补问题

Sty01200818 @ 2024-09-28 03:09:10

14分,没开任何数组为什么会mle,我不理解

#include<stdio.h>
#include<iostream>
using namespace std;
int k,K=1,X,Y;

void other(int x, int y, int dir, int step) {

    if (step == 0) {
        printf("%d %d %d\n", x, y, dir);
        return;
    }
    else {
        if (dir == 1){
            other(x + step, y + step, 1, step - 1);
            other(x -1-step, y + step, 3, step - 1);
            other(x + step, y -1-step, 2, step - 1);
        }
        if (dir == 3){
            other(x - step, y + step, 3, step - 1);
            other(x + 1+step, y + step, 1, step - 1);
            other(x - step, y - 1-step, 4, step - 1);
        }
        if (dir ==2){
            other(x + step, y - step, 2, step - 1);
            other(x + step, y + step+1, 1, step - 1);
            other(x - step - 1, y - step, 4, step - 1);
        }
        if (dir == 4){
            other(x - step, y - step, 4, step - 1);
            other(x - step, y + step+1, 3, step - 1);
            other(x + step+1, y - step, 2, step - 1);
        }
        other(x, y, dir, step - 1);
    }
}

void sol(int x1, int y1,int x2,int y2,int size) {
    K = K / 2;
    size--;
    if (x1 == x2 && x1 == X && y1 == y2 && y1 == Y)return;
    if (X <= x1 + x2 - K - 1 && Y <= y1 + y2 - K - 1) {
        //printf("P在4区\n");
        other(x1 + x2 - K, y1 + y2 - K, 1, size );
        sol(x1, y1, x1 + x2 - K - 1, y1 + y2 - K - 1, size);
    }
    else if (X > x1 + x2 - K - 1 && Y <= y1 + y2 - K - 1) {
        //printf("P在2区\n");
        other(x1 + x2 - K - 1, y1 + y2 - K, 3, size);
        sol(x1+x2-K, y1, x2, y1 + y2 - K , size);
    }
    else if (X <= x1 + x2 - K - 1 && Y > y1 + y2 - K - 1) {
        //printf("P在3区\n");
        other(x1 + x2 - K, y1 + y2 - K - 1, 2, size);
        sol(x1, y1 + y2 - K, x1 + x2 - K - 1, y2, size);
    }
    else if (X > x1 + x2 - K - 1 && Y > y1 + y2 - K - 1) {
        //printf("P在1区\n");
        other(x1 + x2 - K-1, y1 + y2 - K - 1, 4, size);
        sol(x1 + x2 - K, y1 + y2 - K, x2, y2, size);
    }
}

int main() {
    cin >> k >> X >> Y;
    for (int i = 1; i <= k; i++) {
        K *= 2;
    }
    sol(1, 1, K, K, k);

    return 0;
}

by forgotmyhandle @ 2024-09-28 03:42:56

@Sty01200818 无限递归了,把栈空间爆了,就 MLE 了。


by liruizhou_lihui @ 2024-09-28 08:18:08

@Sty01200818 栈溢出


by Hootime @ 2024-09-28 08:21:16

@Sty01200818 递归层数过深导致的栈溢出


by 24ccinteresting @ 2024-10-19 11:05:02

栈溢出了


|