글 읽기 - 반례를 도저히 못찾겠습니다. dfs + dp 를 사용하였습니다.

ojh4110 5년 전 0

사이클 dfs에 사이클 탐지 + dp 를 섞어서 풀었습니다.

진입시 visit = 1 종료시 visit =2

만약 진입중에 한번 더 진입을 하였을 경우 사이클을 탐지해서 전부 종료하고 -1을 리턴 하였습니다.

사이클이 없는 경우에는 memo에 계속 누적되어 중복 탐색을 방지 하였습니다..

게시판의 질문글을 다 뒤져보고 제가 테스트 케이스들을 만들어 봐도 도저히 어디서 틀렸는지 모르겠습니다..

도와주시면 감사하겠습니다..

#include <vector>
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

int N, M;
int map[55][55];
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
int memo[55][55];

int visit[55][55];


bool isSafe(int i, int j) {
    if (i < 0 || j < 0 || i >= N || j >= M) return false;
    else return true;
}

bool isCycle = false;
int ans = 0;

int dfs(int i, int j) {

    if (visit[i][j] == 1) {
        isCycle = true;
        return 0;
    }

    if (memo[i][j] != -1)
        return memo[i][j];
    if (map[i][j] == 0) {
        memo[i][j] = 0;
        return 0;
    }

    visit[i][j] = 1;


    int max_num = 0;
    for (int k = 0; k < 4; ++k) {
        int newI = i + map[i][j] * di[k], newJ = j + map[i][j] * dj[k];
        if (!isSafe(newI, newJ)) max_num = max(max_num, 1);
        else if (!isCycle) {
            max_num = max(max_num, dfs(newI, newJ) + 1);
        }
    }
    memo[i][j] = max_num;
    ans = max(ans, max_num);

    visit[i][j] = 2;
    return max_num;

}

int main() {
#ifdef OHDEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> N >> M;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            char buf;
            cin >> buf;
            if (buf >= '1' && buf <= '9') {
                map[i][j] = buf - '0';
            } else {
                map[i][j] = 0;
            }

            memo[i][j] = -1;
        }
    }


    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (memo[i][j] == -1)
                dfs(i, j);
        }
    }



    if (!isCycle)
        cout << ans;
    else
        cout << -1;
}

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

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다. dfs + dp 를 사용하였습니다.

ojh4110 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말