글 읽기 - 반례 찾습니다.

silvanas 5년 전 0

오늘도 수고가 많으십니다.

나와있는 예제 케이스들은 다 돌려보았으며

TC도 구해서 작은것들은 다 돌려보았으나 반례를 찾지 못하였습니다.

도무지 어디서 놓치고있는지 알 수가 없는데 도와주시면 감사하겠습니다.

BFS로 구현하였으며

1.불번지고

2.유저 이동

식으로 구현하였습니다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int T, W, H;
char map[1001][1001];
int visit[1001][1001];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int BFS(queue<pair<int, int > > fire, queue<pair<int, int > > user){
    visit[user.front().first][user.front().second] = 1;
    int size = fire.size();
    int size2 = user.size();
    while(1){
        //불 번지기
        while(size--){
            int x = fire.front().first;
            int y = fire.front().second;
            fire.pop();
            for(int i = 0 ; i < 4 ; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx > 0 && xx <= H && yy > 0 && yy <= W && map[xx][yy] == '.'){
                    map[xx][yy] = '*';
                    fire.push(make_pair(xx,yy));
                }
            }
        }
        size = fire.size();
        //유저이동
        while(size2--){
            int x = user.front().first;
            int y = user.front().second;
            user.pop();
            if(x == 0 || x == H+1 || y == 0 || y == W+1) return visit[x][y]-1;
            for(int i = 0 ; i < 4 ; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx >= 0 && xx <= H + 1 && yy >= 0 && yy <= W+1 && visit[xx][yy] == 0 && map[xx][yy] == '.'){
                    visit[xx][yy] = visit[x][y] + 1;
                    user.push(make_pair(xx,yy));
                }
            }
        }
        size2 = user.size();
        if(size + size2 == 0) break;
    }
    return -1;
}

int main(){
    cin >> T;
    while(T--){
        cin >> W >> H ;
        queue<pair<int, int > > fire;
        queue<pair<int, int > > user;
        memset(map,'.',sizeof(map));
        memset(visit,0,sizeof(visit));
        for(int i  = 1 ; i <= H ; i++){
            string temp;
            cin >> temp;
            for(int j = 0 ; j < W ; j++){
                map[i][j+1] = temp[j];
                if(map[i][j+1] == '@'){
                    user.push(make_pair(i,j+1));
                }else if(map[i][j+1] == '*'){
                    fire.push(make_pair(i,j+1));
                }
            }
        }
        int answer = BFS(fire,user);
        if(answer == -1){
            cout << "IMPOSSIBLE"<<endl;
        }else{
            cout<<answer<<endl;
        }
    }
    return 0 ;
}

tlwpdus 5년 전 1

작성자님의 풀이에 따르면 map과 visit 배열의 [H+1][.] 또는 [.][W+1] 꼴의 인덱스를 참조해야 하는 것으로 보입니다.

문제의 제한이 H, W<=1000이므로 1001번째 인덱스를 참조할 수 있어야 하고 이를 위해서는 배열을 선언할 때에 적어도 [1002][1002] 크기는 선언해야합니다.

실제로 이 코드에서는 아래와 같은 반례가 있습니다.

W = 1000, H = 1000

##### (###) ####
#@... (...) ...#
#.... (...) ...#
#.... (...) ...#

      (...)

#.... (...) ...#

silvanas 5년 전 1

귀중한 시간 내어 읽어주셔서 정말 감사합니다.

논리는 잘 짰다고 생각했는데, 작은 공간에서만 반례를 찾아서 찾지 못하였던것 같습니다.

와.. 진짜 생각치도 못한곳에서 발견되어 놀랍네요..

이를 경험으로 반례를 더 잘찾을수 있을것 같습니다.

도움주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

반례 찾습니다.

silvanas 5년 전 0

tlwpdus 5년 전 1

silvanas 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말