글 읽기 - 반례에 대해서

namyun1012 1년 전 0

불을 먼저 처리해야 한다고 해서 que 하나에 fire와 me(상근이)를 넣고 돌렸는데 25%에서 계속 틀립니다. 코드가 그 때 그 때 추가하다보니 엉망이 되긴 해서 다시 짤 때는 fire와 me를 따로 돌리고 그 시간을 비교할 생각이긴 한데. 아직 이 코드가 왜 오류가 나는지에 대해서 반례를 못 찾아서 한 번 알아보고 싶습니다. 해당하는 반례를 알려주시면 감사하겠습니다.

q >> q_me 에 들어가있는 값이 fire인지 me인지를 보조해주는 queue

#include <iostream>
#include <string>
#include <queue>
char board[1002][1002];
int dis[1002][1002];
int visited[1002][1002];
int fired[1002][1002];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
//fire 처리 필요
int main() {
    int T;
    std::cin >> T;
    while(T--) {
        std::fill(&board[0][0], &board[1001][1001], NULL);
        std::fill(&dis[0][0], &dis[1001][1001], 0);
        std::fill(&visited[0][0], &visited[1001][1001], 0);
        std::fill(&fired[0][0], &fired[1001][1001], 0);

        std::queue<std::pair<int, int>> q_me;
        std::queue<int> q; // q_me가 me인지 fire인지 확인 me >> 0 fire >> 1

        int w,h;
        std::cin >> w >> h;
        std::string temp;
        std::pair<int, int> temp_me;
        bool isExist = false;

        for(int i = 0 ; i < h; i++) {
            std::cin >> temp;
            for(int j = 0; j < w; j++) {
                board[i][j] = temp[j];
                if(temp[j] == '@') { // Me
                    temp_me = {i,j};
                    visited[i][j] = 1;
                    dis[i][j] = 1;
                    isExist = true;
                }

                if(temp[j] == '*') { // Fire
                    q_me.push({i,j});
                    q.push(1); //
                    visited[i][j] = 1;
                    fired[i][j] = 1;
                }
            }
        }
        //fire 처리를 먼저하고 그 뒤에 me 처리를 하자
        int result = 1e9;
        
        bool check = false; // 빠져나갔을 시
        
        q_me.push(temp_me);
        q.push(0);
        
        while(!q_me.empty()) {
            std::pair<int, int> cur = q_me.front();
            int cur_value = q.front();
            q_me.pop();
            q.pop();
            if(cur_value == 0) {// me 일때
                if(cur.first == h-1 || cur.first == 0 || cur.second == w-1 || cur.second == 0) {
                    result = std::min(result, dis[cur.first][cur.second]);
                    check = true;
                    break;
                }

                

                for(int dir = 0; dir < 4; dir++) {
                    std::pair<int, int> nxt = {cur.first+ dx[dir], cur.second + dy[dir]};
                    if(nxt.first < 0 || nxt.second < 0 || nxt.first >= h || nxt.second >= w) continue;
                    if(board[nxt.first][nxt.second] == '#' || board[nxt.first][nxt.second] == '*' || visited[nxt.first][nxt.second]) continue;
                    visited[nxt.first][nxt.second] = 1;
                    q_me.push({nxt.first, nxt.second});
                    dis[nxt.first][nxt.second] = dis[cur.first][cur.second] + 1;
                    q.push(0);
                }
            }

            else if(cur_value == 1) {
                for(int dir = 0; dir < 4; dir++) {
                    std::pair<int, int> nxt = {cur.first+ dx[dir], cur.second + dy[dir]};
                    if(nxt.first < 0 || nxt.second < 0 || nxt.first >= h || nxt.second >= w) continue;
                    if(board[nxt.first][nxt.second] == '#' || board[nxt.first][nxt.second] == '*' || fired[nxt.first][nxt.second]) continue;
                    visited[nxt.first][nxt.second] = 1;
                    q_me.push({nxt.first, nxt.second});
                    board[nxt.first][nxt.second] = '*';
                    q.push(1);
                }
            }

        }





        if(check) {
            std::cout << result << "\n";
        }
            
        else {
            std::cout << "Impossible" << "\n";
        }

        
    }

    return 0;
}

pill27211 1년 전 0

Impossible -> IMPOSSIBLE 입니다.

namyun1012 1년 전 0

답변 감사합니다!

12%에서는 통과하길래 이런 건 생각도 못했는데 좀 허무하긴 하네요.

코드 로직이 잘못된 줄 알았는데...

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

문제

문제

출처

ICPC

반례에 대해서

namyun1012 1년 전 0

pill27211 1년 전 0

namyun1012 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말