글 읽기 - 왠만한 반례, 테스트 케이스 다 돌아가는데 제출하면 바로 틀립니다..

ojh4110 5년 전 0

다른 질문들 반례 다 넣어보고 돌려도 다 맞다고 나오는데 1%도 안올라가도 틀렸습니다가 나와서 미치겠습니다.. 고수님들 도와주십쇼...

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <list>
//#include <map>
#include <set>

using namespace std;
int N;
int map[105][105];
int visit[105][105];
int make_land_visit[105][105];
int id = 2;
vector<pair<int, int>> go = {
        {0,  1},
        {1,  0},
        {-1, 0},
        {0,  -1}
};

struct item {
    item(int i, int j, int depth) : i(i), j(j), depth(depth) {}

    int i;
    int j;
    int depth;
};

int make_land(int i, int j) {
    queue<pair<int, int>> queue1;
    queue1.emplace(i, j);
    while (!queue1.empty()) {
        int i, j;
        i = queue1.front().first;
        j = queue1.front().second;
        queue1.pop();
        map[i][j] = id;


        for (auto go1 : go) {
            int ii = go1.first + i;
            int jj = go1.second + j;
            if (make_land_visit[ii][jj] == 0 && ii >= 0 && jj >= 0 && ii != N && jj != N && map[ii][jj] == 1) {
                queue1.emplace(ii, jj);
                make_land_visit[ii][jj] = 1;
            }
        }

    }
}

int findNewland(int i, int j, int id) {
    queue<item> queue1;
    queue1.emplace(i, j, 0);
//    memset(visit, 0, sizeof(visit));
    for (int k = 0; k < N; ++k) {
        for (int l = 0; l < N; ++l) {
            visit[k][l] = 0;
        }
    }
    while (!queue1.empty()) {
        int i, j, depth;
        i = queue1.front().i;
        j = queue1.front().j;
        depth = queue1.front().depth;
        queue1.pop();
        if (map[i][j] != 0 && id != map[i][j]) {
            return depth;
        }

        for (auto go1 : go) {
            int ii = go1.first + i;
            int jj = go1.second + j;
            if (visit[ii][jj] == 0 && ii >= 0 && jj >= 0 && ii != N && jj != N &&
                (map[ii][jj] == 0 || map[ii][jj] != id)) {
                queue1.emplace(ii, jj, depth + 1);
                visit[ii][jj] = 1;
            }
        }

    }
}

int main() {
    cin >> N;
    int result = 2100000000;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> map[i][j];
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            if (map[k][i] == 1) {
                make_land(k, i);
                id++;
            }
        }
    }
    for (int l = 0; l < N; ++l) {
        for (int i = 0; i < N; ++i) {
            if (map[l][i] != 0) {
                result = min(findNewland(l, i, map[l][i]), result);
            }
        }
    }
    cout << result - 1;
}

djm03178 5년 전 1

findNewland 함수가 다른 섬을 찾지 못하고 (예를 들면, 자기 자신의 섬에 가로막히는 경우) 루프를 빠져나오는 경우 아무것도 리턴할 것이 명시되어 있지 않습니다. 85번째 줄 이후에 return 10000; 을 추가하면 맞습니다.

그와는 별개로 매우 위험한 코드가 있는데 47, 78번째 줄에서 visit[ii][jj]를 먼저 접근하고 있는데 ii나 jj가 음수인 경우 이는 배열의 범위를 벗어난 접근이 됩니다. 운이 나쁘면 곧바로 런타임 에러로 이어질 가능성이 있습니다. 반드시 ii >= 0 && jj >= 0 && ii != N && jj != N 체크를 먼저 (&& 연산자의 왼쪽에) 해야 합니다.

ojh4110 5년 전 0

djm03178님 친절한 답변 감사드립니다... 고수시군요.. 더욱 정진하여 알린이 벗어 나겠습니다! 감사합니다

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

문제

문제

출처

ICPC

왠만한 반례, 테스트 케이스 다 돌아가는데 제출하면 바로 틀립니다..

ojh4110 5년 전 0

djm03178 5년 전 1

ojh4110 5년 전 0

djm03178님 친절한 답변 감사드립니다... 고수시군요.. 더욱 정진하여 알린이 벗어 나겠습니다! 감사합니다

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말