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

seung7361 2일 전 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;
}

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

문제

문제

출처

ICPC

반례가 있을까요?

seung7361 2일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말