글 읽기 - 틀린 케이스를 알 수 있을까요?

shie44167 7년 전 0

점화식은

d[i][j] = j는 i번째 좌표 중심과 주변 4개의 근접한 점 에서의 경로의 최소값 이라 했습니다만, 몇퍼센트 올라가다가 틀렸다고 합니다. 도와주세요

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

vector<pair<int, int>> v;
long long d[100001][5];
int mov[2][5] = {
	{ 0, -1, 1, 0, 0 },
	{ 0, 0, 0, -1, 1 }
};

int main() {
	int n; scanf("%d", &n);
	for (int i = 0; i <= n; i++) {
		int a, b; scanf("%d%d", &a, &b);
		v.push_back(make_pair(a, b));
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < 5; j++) {
			d[i][j] = -1;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 5; j++) {
			int px = v[i].first + mov[0][j];
			int py = v[i].second + mov[1][j];

			if (px >= 0 && py >= 0 && px <= 100000 && py <= 100000) {
				for (int k = 0; k < 5; k++) {
					int nx = v[i - 1].first + mov[0][k];
					int ny = v[i - 1].second + mov[1][k];

					if (nx >= 0 && ny >= 0 && nx <= 100000 && ny <= 100000) {
						if (i != 1) {
							long long num = d[i - 1][k] + abs(px - nx) + abs(py - ny);

							if (d[i][j] == -1 || d[i][j] > num)
								d[i][j] = num;
						}
						else {
							long long num = abs(px - v[i - 1].first) + abs(py - v[i - 1].second);

							if (d[i][j] == -1 || d[i][j] > num)
								d[i][j] = num;
						}
					}
				}
			}
		}
	}

	long long ans = 0x7ffffffffff;

/*	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < 5; j++) {
			printf("%lld ", d[i][j]);
		}
		printf("%\n");
	}*/

	for (int i = 0; i < 5; i++) {
		if (ans > d[v.size() - 1][i])
			ans = d[v.size() - 1][i];
	}

	printf("%lld\n", ans);
}

shie44167 7년 전 0

해결 했습니다 마지막 부분에 문제가 생길 수가 있다는걸 알 수 있었습니다 감사합니다

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

문제

문제

출처

ICPC

틀린 케이스를 알 수 있을까요?

shie44167 7년 전 0

shie44167 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말