글 읽기 - 61%에서 틀립니다. 제발 도와주세요 고수님들 ㅜㅜ

uiucpass 5년 전 0

isRotate는 BBB 에서 중간 B를 중심으로 회전할 수 있는지 체크하는 함수이고

mat이라는 2차원배열은 1과 0만이 있습니다.(B나 E도 0)

visited는 [row 위치][column 위치] [ 방향] 으로 이루어져있습니다.

지도를 입력 받고, 입력받은 BBB의 중간 B의 위치를 큐에 넣고, 처음위치부터 rotate가능한 지 확인한 뒤에

BFS를 실행합니다. 여기서 큐는 row, col, 얼마나 이동했는지(cnt), 수직으로 가는지 평행으로가는지 (chk) 를

각각 요소로 가지고 있는 struct를 원소로 가집니다. BFS가 시작되면 큐의 front()에서 왼쪽 오른쪽 위 아래를 검사하고

방문한 것이 아니면 cnt + 1을 하고, 여기서 rotate 까지 가능하면 cnt + 2를 하여 줍니다.

마지막으로 E와 같은 방향( 수직 or 평행)이면서 E의 중간 지점과 탐색하는 위치가 일치하면 즉시 종료하고, 탐색 중인

cnt를 출력합니다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int N;
bool isMove = false;

struct con{
    int r;
    int c;
    int ct;
    int chk;
};

int rl[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int ud[8] = {1, -1, 0, 0, 1, -1, 1, -1};

vector<vector<int>> mat;
vector<vector<int>> paddler;

bool visited[52][52][2];

    //1 -> vertical
    //0 -> hortizental
    
bool isRotate(int row, int col){
    bool isTree = true;
    for (int i = 0; i < 8; i++)
    {
        if (mat[row + ud[i]][col + rl[i]] == 1)
        {
            isTree = false;
            break;
        }
    }
    return isTree;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> N;
    mat.resize(N + 2, vector<int>(N + 2, 1));
    paddler.resize(N + 2, vector<int>(N + 2, 0));

    vector<con> B;
    vector<con> E;

    string in;

    for (int i = 1; i <= N; i++){
        cin >> in;
        for (int j = 0; j < in.length(); j++){
            if (in[j] == '1') mat[i][j + 1] = 1;
            else if (in[j] == 'B'){
                mat[i][j + 1] = 0;
                B.push_back({i, j + 1, 0, 0});
            }
            else if (in[j] == 'E'){
                mat[i][j + 1] = 0;
                E.push_back({i, j + 1, 0, 0});
            }
            else mat[i][j + 1] = 0; 
        }
    }

    queue<con> q;

    if(E[0].r == E[1].r && E[1].r == E[2].r
    && E[0].c + 1 == E[1].c && E[1].c + 1 == E[2].c) E[1].chk = 0;
    else if(E[0].c == E[1].c && E[1].c == E[2].c
    && E[0].r + 1 == E[1].r && E[1].r + 1 == E[2].r) E[1].chk = 1;
    else {
        printf("0");
        return 0;
    }

    if(B[0].r == B[1].r && B[1].r == B[2].r
    && B[0].c + 1 == B[1].c && B[1].c + 1 == B[2].c) q.push(B[1]);
    else if(B[0].c == B[1].c && B[1].c == B[2].c
    && B[0].r + 1 == B[1].r && B[1].r + 1 == B[2].r) {
        B[1].chk = 1;
        q.push({B[1].r, B[1].c, 0, B[1].chk});
    }
    else{
        printf("0");
        return 0;
    }
    visited[B[1].r][B[1].c][B[1].chk] = true;
    paddler[B[1].r][B[1].c] = B[1].chk;
    if (isRotate(B[1].r, B[1].c)){
        q.push({B[1].r, B[1].c, B[1].ct + 1, 1 - B[1].chk});
        visited[B[1].r][B[1].c][1- B[1].chk];
    }

    while(q.size()){
        int row = q.front().r;
        int col = q.front().c;
        int cnt = q.front().ct;
        int chk = q.front().chk;

        cout << row << " " << col << " " << cnt << " " << chk << endl;

        if(row == E[1].r && col == E[1].c && chk == E[1].chk){
            printf("%d", cnt);
            isMove = true;
            break;
        }

        for(int i = 0; i < 4; i++){
            int _row = row + ud[i];
            int _col = col + rl[i];

            if(mat[_row][_col] == 1) continue;
            else if(chk == 1){
                if(mat[_row + 1][_col] == 1 || mat[_row - 1][_col] == 1) continue;
                if(visited[_row][_col][chk]) continue;
                q.push({_row, _col, cnt + 1, chk});
                visited[_row][_col][chk] = true;
                if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
                    q.push({_row, _col, cnt + 2, 1 - chk});
                    visited[_row][_col][1 - chk] = true;
                }
            }
            else if(chk == 0){
                if(mat[_row][_col + 1] == 1 || mat[_row][_col - 1] == 1) continue;
                if(visited[_row][_col][chk]) continue;
                q.push({_row, _col, cnt + 1, chk});
                visited[_row][_col][chk] = true;
                if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
                    q.push({_row, _col, cnt + 2, 1 - chk});
                    visited[_row][_col][1 - chk] = true;
                }
            }
        }
        q.pop();
    }

    if(!isMove) cout << 0;

    return 0;
}

jh05013 5년 전 1

https://ideone.com/Lc8cig

jh05013 5년 전 1

디버깅용 printf를 다 지웠을 경우의 반례입니다.

uiucpass 5년 전 0

jh05013

님 정말 감사합니다 ㅜㅜㅜ 사랑합니다!!!!!!!!!!!!!!!!!!!!!!!!

혹시 반례같은 건 어떻게 찾으시는 지 여쭈어도 될까요?

jh05013 5년 전 0

방금은 랜덤 데이터를 만들어서 제 코드와 비교했고, 그냥 아무렇게나 넣다 보면 나오는 경우도 많습니다.

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

문제

문제

출처

ICPC

61%에서 틀립니다. 제발 도와주세요 고수님들 ㅜㅜ

uiucpass 5년 전 0

jh05013 5년 전 1

jh05013 5년 전 1

uiucpass 5년 전 0

jh05013

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말