글 읽기 - 파이프 문제 재귀로 풀었는데 틀렸습니다가 발생합니다

bbb1293 4년 전 0

브루트 포스로 분류되길래 재귀로 풀었습니다.

flag로 가로, 세로, 대각선을 표시하였고 각각의 케이스를 if문으로 분류하였습니다.

문제에서 제시한 예제는 다 맞게 나오는데 어느부분이 틀렸는지 질문드리고 싶습니다.

#include<iostream>

using namespace std;

int n;
int house[18][18];

int number_move(int y, int x, int flag) {

    if (y == n && x == n) {
        return 1;
    }

    if (y > n || x > n) {
        return 0;
    }

    if (flag == 0) {
        if (!house[y][x + 1]) {
            if (!house[y + 1][x + 1] && !house[y + 1][x]) {
                return number_move(y, x + 1, 0) + number_move(y + 1, x + 1, 2);
            }
            return number_move(y, x + 1, 0);
        }
        return 0;
    }

    if (flag == 1) {
        if (!house[y + 1][x]) {
            if (!house[y + 1][x + 1] && !house[y][x + 1]) {
                return number_move(y + 1, x, 1) + number_move(y + 1, x + 1, 2);
            }
            return number_move(y + 1, x, 0);
        }
        return 0;
    }

    if (flag == 2) {
        if (!house[y][x + 1]) {
            if (!house[y + 1][x] && !house[y + 1][x + 1]) {
                return number_move(y + 1, x, 1) + number_move(y, x + 1, 0) + number_move(y + 1, x + 1, 2);
            }
            if (!house[y + 1][x]) {
                return number_move(y + 1, x, 1) + number_move(y, x + 1, 0);
            }
            return number_move(y, x + 1, 0);
        }

        if (!house[y + 1][x]) {
            return number_move(y + 1, x, 1);
        }

        return 0;
    }

    return 0;
}

int main() {

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &house[i + 1][j + 1]);
        }
    }

    printf("%d", number_move(1, 2, 0));

    return 0;
}

sait2000 4년 전 0

뭐가 문제인지는 아직 코드를 안 봤고 반례는 몇 개 찾았습니다.

in1:
6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0

out1:
10

in2:
6
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0

out2:
3

note2:
* * 0 0 0 0
0 0 * 0 1 0
0 0 * 1 0 0
0 0 * 0 0 0
0 0 * 0 0 0
0 1 0 * * *

* * 0 0 0 0
0 0 * 0 1 0
0 0 * 1 0 0
0 0 * 0 0 0
0 0 0 * 0 0
0 1 0 0 * *

* * 0 0 0 0
0 0 * 0 1 0
0 0 * 1 0 0
0 0 * 0 0 0
0 0 0 * * 0
0 1 0 0 0 *

in3:
6
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 1 0 0 0 0

out3:
1

note3:
* * 0 0 0 0
0 0 * 0 1 0
0 0 * 1 0 0
0 0 * 0 0 0
0 0 * 0 1 0
0 1 0 * * *

sait2000 4년 전 0

33번 줄이 문제같네요.

bbb1293 4년 전 0

오 감사합니다!

33번 줄 flag를 고치니 정답이 되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이프 문제 재귀로 풀었는데 틀렸습니다가 발생합니다

bbb1293 4년 전 0

sait2000 4년 전 0

sait2000 4년 전 0

bbb1293 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말