글 읽기 - 테스트케이스, 게시판에서 반례는 정답인데 틀렸다고 나옵니다

hannnn 4년 전 0

테스트케이스와 게시판에서 여러 반례를 찾아다가 시도해보고 성공을 확인했는데

틀렸다고 나오네요 ㅠㅠ

어디서 틀렸는지 알 수 있을까요?

#include <queue>
#include <iostream>
#include <cstdio>

#define max_int 51

using namespace std;

char m[max_int][max_int];
int flood_time[max_int][max_int];
int visit[max_int][max_int];

int dx[4] = {1, 0, -1, 0}; // 고슴도치 이동 & 물 확장에서 사용
int dy[4] = {0, 1, 0, -1};

int main(){
    int r, c;
    cin >> r >> c;
    /*
    비어있는 곳 '.'
    물이 차있는 지역 '*'
    돌 'X'
    비버의 굴 'D'
    고슴도치의 위치 'S'
    */
    int start_x = 0; int start_y = 0;
    int end_x = 0; int end_y = 0;
    queue<pair<int,int>> water_q;
    queue<pair<int,int>> q;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> m[i][j];
            
            if(m[i][j] == 'S'){
                q.push({i,j});
            }
            else if(m[i][j] == 'D'){
                end_x = i;
                end_y = j;
            }
            else if(m[i][j] == '*'){
                water_q.push({i,j});
            }
        }
    }
    
        // 물 업데이트
    while(!water_q.empty()){
        int w_x = water_q.front().first; 
        int w_y = water_q.front().second;
        water_q.pop();

        for(int i=0; i<4; i++){
            int w_nx = w_x + dx[i];
            int w_ny = w_y + dy[i];
            if(w_nx < 0 || w_nx >= r || w_ny < 0 || w_ny >= c) continue; // 범위 밖 처리
            if(flood_time[w_nx][w_ny] == 0 && m[w_nx][w_ny] =='.'){ // 물 넘친적없고, 갈 수 있는곳
                flood_time[w_nx][w_ny] = flood_time[w_x][w_y] + 1;
                water_q.push({w_nx, w_ny});
            }
        }
    }

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){ 
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx == end_x && ny == end_y){
                cout << visit[x][y]+1;
                return 0;
            }

            if(nx < 0 || nx >= r || ny < 0 || ny >=c) continue; // 범위 밖 처리
            if(visit[nx][ny] == 0 && m[nx][ny] == '.' && (visit[x][y]+1) < flood_time[nx][ny]){
                visit[nx][ny] = visit[x][y] + 1;
                q.push({nx,ny});
            }
        }
    }

    cout << "KAKTUS";
    return 0;
}

seico75 4년 전 2

두 군데의 문제가 있는 것 같아서.. (연관이 되어 있지만..)

두개의 반례를 드립니다.

5 5
*.XS.
..X..
..X..
..X..
..X.D

5 5
*.X..
..X..
..S..
..X..
..X.D

hannnn 4년 전 0

seico75님 감사합니다.

덕분에 해결했습니다~ ^^

mraz3068 2년 전 0

감사합니다~

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

문제

문제

출처

ICPC

테스트케이스, 게시판에서 반례는 정답인데 틀렸다고 나옵니다

hannnn 4년 전 0

seico75 4년 전 2

hannnn 4년 전 0

mraz3068 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말