글 읽기 - 경찰차 질문입니다.

cubalys 6년 전 0

F(x, y)를 1번차가 x사건에 2번차가 y사건에 있을 때 W사건까지 거리의 최소 라고 생각하고 작성했습니다.

경로의 경우는 0 0 부터 시작하여 갈수 있는 경로의 DP배열에 저장된 값중 더 작은 값을 따라가며 출력했습니다.

제 생각에는 맞게 작성한 것 같은데 어느부분에서 문제가 생긴건지 궁금하네요

#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, W, w[1001][2], DP[1001][1001];

int dis(int x, int y){
	return abs(w[x][1] - w[y][1]) + abs(w[x][0] - w[y][0]);
}

int F(int x, int y){
	int m = x > y ? x : y;
	if (m == W) return 0;
	int &ret = DP[x][y];
	if (ret != INF) return ret;
	w[0][0] = w[0][1] = 1;
	ret = min(ret, F(m + 1, y) + dis(x, m + 1));
	w[0][0] = w[0][1] = N;
	ret = min(ret, F(x, m + 1) + dis(y, m + 1));
	return ret;
}

void route(int x, int y){
	int m = x > y ? x : y, a, b;
	if (m == W) return ;
	w[0][0] = w[0][1] = 1;
	a = DP[m + 1][y] + dis(x, m + 1);
	w[0][0] = w[0][1] = N;
	b = DP[x][m + 1] + dis(y, m + 1);
	if (a > b) printf("%d\n", 2), route(x, m + 1);
	else printf("%d\n", 1), route(m + 1, y);
}

int main(){
	for (int i = 0; i < sizeof(DP) / 4; i++)
		*(&DP[0][0] + i) = INF;
	scanf("%d%d", &N, &W);
	for (int i = 1; i <= W; i++)
		scanf("%d%d", &w[i][0], &w[i][1]);
	printf("%d\n", F(0, 0));
	route(0, 0);
}

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

문제

문제

출처

ICPC

경찰차 질문입니다.

cubalys 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말