글 읽기 - 샘플은 다맞는데 반례를 못찾겠어요 ㅜㅜ

darrenc 5년 전 0

뭐가 잘못된 걸까요? 답답하네요 ㅜㅜ

#include<bits/stdc++.h>

using namespace std;
int r, c;
char forest[51][51];
int flood[51][51];
int goseum[51][51];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue<pair<int, int> > wat, mou;
int eny, enx;
int main(){
    scanf("%d %d", &r, &c);
    memset(flood, -1, sizeof(flood));
    memset(goseum, -1, sizeof(goseum));
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> forest[i][j];
            flood[i][j] = goseum[i][j] = -1;
            if(forest[i][j] == '*'){ wat.push(make_pair(i, j)); flood[i][j] = 0;}
            if(forest[i][j] == 'S') {mou.push(make_pair(i, j)); goseum[i][j] = 0;}
            if(forest[i][j] == 'D'){
                eny = i; enx = j;
            }
        }
    }
    while(!wat.empty()){
        int cy = wat.front().first;
        int cx = wat.front().second;
        wat.pop();
        for(int i = 0; i < 4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny >= 0 && ny < r && nx >= 0 && nx < c){
                if(flood[ny][nx] == -1){
                    if(forest[ny][nx] == '.' || forest[ny][nx] == 'S'){
                        flood[ny][nx] = flood[cy][cx] + 1;
                        wat.push(make_pair(ny, nx));
                    }
                }
            }
        }
    }
    while(!mou.empty()){
        int cy = mou.front().first;
        int cx = mou.front().second;
        mou.pop();
        for(int i = 0; i < 4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny >= 0 && ny < r && nx >= 0 && nx < c){
                if(goseum[ny][nx] == -1 && forest[ny][nx] == '.'){
                    if(goseum[cy][cx] + 1 < flood[ny][nx]){
                        goseum[ny][nx] = goseum[cy][cx] + 1;
                        mou.push(make_pair(ny, nx));
                    }
                }
                if(ny == eny && nx == enx){
                    goseum[ny][nx] = goseum[cy][cx] + 1;
                }
            }
        }
    }
    if(goseum[eny][enx] == -1){
        printf("KAKTUS\n");
    }else {
        printf("%d\n", goseum[eny][enx]);
    }
}

adfsfsf 5년 전 2

5 7

S....X*

.XXX.X.

..X..X.

X.X.XX.

X...DX.

이와 같은 경우 답은 8인데 작성자님 코드는 KAKTUS를 출력합니다.

adfsfsf 5년 전 0

53번 줄에서 goseum[cy][cx] + 1 < flood[ny][nx] 대신 (goseum[cy][cx] + 1 < flood[ny][nx] || flood[ny][nx] == -1)로 바꿔주셔야 합니다.

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

문제

문제

출처

ICPC

샘플은 다맞는데 반례를 못찾겠어요 ㅜㅜ

darrenc 5년 전 0

adfsfsf 5년 전 2

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말