글 읽기 - 70%에서 틀리네요. 반례가 있을까요?

kchung1995 3년 전 0

제 코드가 어느 부분이 잘못됐는지 모르겠습니다.

dfs를 이용한 완전탐색으로 구현했고 게시판의 모든 반례를 다 테스트해 본 것 같은데,

딱 70%에서 틀립니다.

반례가 어떤 게 있을지, 혹은 어느 부분에서 문제가 되는 것인지 궁금합니다.

#include <iostream>
using namespace std;
#define MAX_N 10

int n, m, turn = 1e9;

void array_copy (char from[][MAX_N], char to[][MAX_N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            to[i][j] = from[i][j];
        }
    }
}

void simulate(int index, char arr[][MAX_N], int dir) {
    char copy[MAX_N][MAX_N];
    array_copy(arr, copy);
    
    if (index == 10) return;
    bool blueEnter = false, redEnter = false;
    if (dir == 0) {                                         //왼쪽으로 기울일 때
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (copy[i][j] == 'B' || copy[i][j] == 'R') {
                    char now = copy[i][j];
                    for (int k = j; k > 0; k--) {
                        if (copy[i][k-1] == '.') {
                            swap(copy[i][k], copy[i][k-1]);
                            continue;
                        }
                        else if (copy[i][k-1] == 'O') {
                            if (now == 'B') blueEnter = true;
                            else if (now == 'R') redEnter = true;
                            copy[i][k] = '.';
                            break;
                        }
                        else break;
                    }
                }
            }
        }
    }
    else if (dir == 1) {                                    //오른쪽으로 기울일 때
        for (int i = 0; i < n; i++) {
            for (int j = m-2; j >= 0; j--) {
                if (copy[i][j] == 'B' || copy[i][j] == 'R') {
                    char now = copy[i][j];
                    for (int k = j; k < m; k++) {
                        if (copy[i][k+1] == 'O') {
                            if (now == 'B') blueEnter = true;
                            else if (now == 'R') redEnter = true;
                            copy[i][k] = '.';
                            break;
                        }
                        else if (copy[i][k+1] == '.') {
                            swap(copy[i][k], copy[i][k+1]);
                            continue;
                        }
                        else break;
                    }
                }
            }
        }
    }
    else if (dir == 2) {                                    //위쪽으로 기울일 때
        for (int j = 0; j < m; j++) {
            for (int i = 1; i < n; i++) {
                if (copy[i][j] == 'B' || copy[i][j] == 'R') {
                    char now = copy[i][j];
                    for (int k = i; k > 0; k--) {
                        if (copy[k-1][j] == '.') {
                            swap(copy[k][j], copy[k-1][j]);
                            continue;
                        }
                        else if (copy[k-1][j] == 'O') {
                            if (now == 'B') blueEnter = true;
                            else if (now == 'R') redEnter = true;
                            copy[k][i] = '.';
                            break;
                        }
                        else break;
                    }
                }
            }
        }
    }
    else if (dir == 3) {                                    //아래쪽으로 기울일 때
        for (int j = 0; j < m; j++) {
            for (int i = n-2; i >= 0; i--) {
                if (copy[i][j] == 'B' || copy[i][j] == 'R') {
                    char now = copy[i][j];
                    for (int k = i; k < n; k++) {
                        if (copy[k+1][j] == 'O') {
                            if (now == 'B') blueEnter = true;
                            else if (now == 'R') redEnter = true;
                            copy[k][j] = '.';
                            break;
                        }
                        else if (copy[k+1][j] == '.') {
                            swap(copy[k][j], copy[k+1][j]);
                            continue;
                        }
                        else break;
                    }
                }
            }
        }
    }

    if (redEnter && !blueEnter) {
        turn = min(turn, index + 1);
        return;
    }
    else if (blueEnter) return;
    
    for (int nextDir = 0; nextDir < 4; nextDir++) {
        if (dir == nextDir) continue;
        simulate(index+1, copy, nextDir);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    char board[MAX_N][MAX_N];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {                           //세로
        for (int j = 0; j < m; j++) {                       //가로
            cin >> board[i][j];
        }
    }
    
    for (int dir = 0; dir < 4; dir++) {
        simulate(0, board, dir);
    }
    
    if (turn == 1e9) cout << -1;
    else cout << turn;
    return 0;
}

kchung1995 3년 전 0

자답합니다.

78번째 줄에 copy[k][i] 가 아니라 copy[k][j]여야 했는데 오타였네요.

사용한 반례입니다.

9 9

#########

###.....#

#..#..#O#

##..R.#B#

####....#

#.....#.#

#.#.....#

##.###..#

#########

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

문제

문제

출처

ICPC

70%에서 틀리네요. 반례가 있을까요?

kchung1995 3년 전 0

kchung1995 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말