글 읽기 - 어떤 케이스에서 틀린건가요?

ajax0615 6년 전 0

ㅇㅓ떤 케이스에서 틀린건지 잘 모르겠습니다..

고수님들 도와주세요 ㅜㅜ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int DIR[4][2] = {
    0, 1,
    1, 0,
    -1, 0,
    0, -1
};
const int JUMP[8][2] = {
    -2, -1,
    -1, -2,
    1, -2,
    2, -1,
    2, 1,
    1, 2,
    -1, 2,
    -2, 1
};
const int INF = 987654321;
const int MAX_DIST = 44444;
struct Node {
    int x, y, power;
    Node() : x(0), y(0), power(0) {}
    Node(int x, int y, int power) : x(x), y(y), power(power) {}
};
int k, dist;
vector<vector<int> > map;
vector<vector<int> > visited;
vector<vector<vector<int> > > cache;

bool canGo(int x, int y) {
    if (x < 0 || x > map[0].size() - 1) return false;
    if (y < 0 || y > map.size() - 1) return false;
    if (1 == map[y][x]) return false;
    if (visited[y][x]) return false;
    return true;
}

int tour(int x, int y, int p) {
    if (x < 0 || x > map[0].size() - 1) return INF;
    if (y < 0 || y > map.size() - 1) return INF;
    if (x == map[0].size() - 1 && y == map.size() - 1) return 0;

    int &ret = cache[x][y][p];
    if (-1 != ret) return ret;
    ret = INF;
    visited[y][x] = 1;
    for (int d = 0; d < 4; ++d) {
        for (int j = 0; j < 8; ++j) {
            Node next(x + DIR[d][0], y + DIR[d][1], p);
            if (canGo(next.x, next.y)) {
                ret = min(ret, 1 + tour(next.x, next.y, next.power));
            }
            if (p > 0) {
                Node next2(x + JUMP[j][0], y + JUMP[j][1], p - 1);
                if (canGo(next2.x, next2.y)) {
                    ret = min(ret, 1 + tour(next2.x, next2.y, next2.power));
                }
            }
        }
    }
    visited[y][x] = 0;
    return ret;
}

int main() {
    cin >> k;
    int width, height; cin >> width >> height;
    map.assign(height, vector<int>(width, 0));
    visited.assign(height, vector<int>(width, 0));
    cache.assign(height + 1, vector<vector<int> >(width + 1, vector<int> (k + 1, -1)));
    for (int y = 0; y < height; ++y) {
        for (int x = 0; x < width; ++x) {
            cin >> map[y][x];
        }
    }
    int ret = tour(0, 0, k);
    if (INF == ret) ret = -1;
    cout << ret << endl;
    return 0;
}

zlzmsrhak 6년 전 0

반례입니다. 메모이제이션으로 DP 문제를 풀 때는 visited 같은 함수를 쓰면 안됩니다.

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

문제

문제

출처

ICPC

어떤 케이스에서 틀린건가요?

ajax0615 6년 전 0

zlzmsrhak 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말