글 읽기 - c++ 2퍼 이후에서 틀리는데 반례가 있나요?

pushrsp 1년 전 0

예제는 다 통과했는데 제출하면 2퍼 이후에서 틀렸다고 하는데 문제가 뭔지 모르겠네요

#include <iostream>
#include <queue>

using namespace std;

int M, N, H;
int tomato[101][101][101];
bool visited[101][101][101];
int day[101][101][101];

/*
 * 1 익은 토마토
 * 0 익지 않은 토마토
 * -1 토마토가 들어있지 않은 칸
 */

struct Pos {
public:
    Pos operator+(const Pos &other) const {
        Pos ret{y + other.y, z + other.z, x + other.x};
        return ret;
    }

    bool operator==(const Pos &other) const {
        return y == other.y && z == other.z && x == other.x;
    }

    bool operator<(const Pos &other) const {
        if (y != other.y)
            return y < other.y;
        else if (z != other.z)
            return z < other.z;
        else
            return x < other.x;
    }

public:
    int y;
    int z;
    int x;
};

Pos delta[6] = {
        Pos{-1, 0, 0}, //위
        Pos{1, 0, 0}, //아래
        Pos{0, 0, -1}, //왼쪽
        Pos{0, 0, 1}, //오른쪽
        Pos{0, 1, 0}, //앞
        Pos{0, -1, 0}, //뒤
};

void BFS(Pos pos) {
    queue<Pos> q;
    q.push(pos);
    visited[pos.y][pos.z][pos.x] = true;

    while (!q.empty()) {
        pos = q.front();
        q.pop();

        for (auto i: delta) {
            Pos next = pos + i;

            if (next.y < 1 || next.y > H)
                continue;
            if (next.z < 1 || next.z > N)
                continue;
            if (next.x < 1 || next.x > M)
                continue;
            if (tomato[next.y][next.z][next.x] != 0)
                continue;
            if (visited[next.y][next.z][next.x])
                continue;

            tomato[next.y][next.z][next.x] = 1;
            visited[next.y][next.z][next.x] = true;
            day[next.y][next.z][next.x] = day[pos.y][pos.z][pos.x] + 1;
            q.push(next);
        }
    }
}

int main() {
    cin >> M >> N >> H;

    for (int y = 1; y <= H; ++y) {
        for (int z = 1; z <= N; ++z) {
            for (int x = 1; x <= M; ++x) {
                cin >> tomato[y][z][x];
            }
        }
    }

    for (int y = 1; y <= H; ++y) {
        for (int z = 1; z <= N; ++z) {
            for (int x = 1; x <= M; ++x) {
                if (tomato[y][z][x] == 1 && !visited[y][z][x]) {
                    Pos pos{y, z, x};
                    BFS(pos);
                }
            }
        }
    }

    int result = 0;
    for (int y = 1; y <= H; ++y) {
        for (int z = 1; z <= N; ++z) {
            for (int x = 1; x <= M; ++x) {
                if (tomato[y][z][x] == 0) {
                    cout << -1;
                    return 0;
                }

                if (day[y][z][x] > result)
                    result = day[y][z][x];
            }
        }
    }

    cout << result;
    return 0;
}

kokosoko59 1년 전 10

반례가 될지 모르겠는데

10 1 1
1 0 0 0 0 0 0 0 0 1

이런 예시를 돌려보시면 어떨까요? 정답은 5인데 이 코드에서는 9로 나올지도?

kokosoko59 1년 전 9

위 댓글 수정: 정답은 4인데 이 코드에서는 8로 나올지도?

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

문제

문제

출처

ICPC

c++ 2퍼 이후에서 틀리는데 반례가 있나요?

pushrsp 1년 전 0

kokosoko59 1년 전 10

kokosoko59 1년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말