글 읽기 - 반례가 있을까요?

seung7361 1년 전 0

예제에 있는건 다 잘 나오는데 반례가 혹시 있을까요? ㅠㅠ

그냥 DFS에다가 지금까지 온 경로를 path vector에다가 저장해놓고 가려는 경로가 path vector에 포함되어있다면 안가도록 만들었는데

어떤 반례가 있을까요?? 부탁드립니다 ㅠㅠ

#include <iostream>
#include <vector>

int r, c;
bool ans = false;
std::vector<std::pair<int, int>> path;
int map[5][5] = {0, };

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y, int move_count, int apple) {
    if (move_count >= 4 || ans) return;
    if (map[x][y] == -1) return;
    for (int i = 0; i < path.size(); i++) {
        if (path[i].first == x && path[i].second == y) return;
    }

    if (apple >= 2 && move_count == 3) {
        ans = true;
        return;
    }

    path.push_back(std::make_pair(x, y));
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || ans) continue;
        if (map[x][y] == -1) continue;
        dfs(nx, ny, move_count + 1, apple + map[x][y]);
    }
    path.pop_back();
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            std::cin >> map[i][j];
        }
    }
    std::cin >> r >> c;

    dfs(r, c, 0, 0);
    if (ans) std::cout << 1 << '\n';
    else std::cout << 0 << '\n';

    return 0;
}

choko100 1년 전 2

안녕하세요, 3번 이내 이동으로 가능한지 판단하는 부분에서 반례가 생길 것 같습니다. 19 번 라인에 move_count == 3 인 경우만 체크하게 되어있는데 이걸 move_count <= 3 으로 변경해야할 것 같습니다. 아래와 같이 2번만 이동하고 2번 모두 사과를 먹었지만 더 이상 이동할 수 없는 경우를 커버하지 못합니다.

입력

0 1 1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1 
0 0

정답

위의 코드 출력

seung7361 1년 전 0

1달전에 그 부분 발견해서 그렇게 고쳐봤는데도 그냥 틀렸습니다 뜨네요... solved.ac 디코방에도 물어봤었는데 그냥 코드 구조 자체를 처음부터 잘못짠거 같아요. 그냥 드랍했습니다 (.....)

choko100 1년 전 1

앗...ㅠㅠ... 그래도... 혹시 몰라서... 19 번 라인을 고친 상태라고 가정하고 또 반례를 찾았습니다.

30번과 31번 라인이 다음번에 갈 곳을 대상으로 해야할 것 같은데 현재 위치인 x, y 로 되어있는 것 같습니다. 30번, 31번 라인의 x, y 도 nx, ny 로 하면 아래 반례에 올바른 답이 나옵니다.

입력

0 0 1 1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0

정답

위의 코드 출력

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

문제

문제

출처

ICPC

반례가 있을까요?

seung7361 1년 전 0

choko100 1년 전 2

seung7361 1년 전 0

choko100 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말