B. Driving License

주어진 연료 G 안에 도착점에 최단 시간으로 도착하는 방법을 찾는 문제다. 한 칸 이동을 할 때 L 시간 만큼 걸리고, 방향을 회전할 때 마다 시간이 1 만큼 걸린다. 이 문제에서 아래 방향과 오른쪽 방향으로만 움직일 수 있으므로, 각 위치까지 가는 시간은 여태까지 회전한 회수에 따라 결졍 된다. 즉, r행 c열에 있는 칸까지 k번 회전하였다면 걸린 시간은 총 ((r-1)+(c-1))*L + k 이다. 

따라서, D[r][c][k][d]=현재 위치는 r행 c열, 회전한 회수는 k, 현재 바라보는 방향은 d 일 때 최소 연료 사용량이라 정의하고 Dynamic Programming 을 하면 된다. 시작점에서 도착점까지 이동할 때 방문하는 지점은 많아야 199개 이며, 각 지점에서 회전을 2번 이상하는 것은 비효율적이므로 최대 회전 회수는 200번 정도라고 생각할 수 있다. 시간복잡도는 O(N^3) 이다.

#include <stdio.h> int T, M, N, L, G; int H[101][101], V[101][101], D[101][101][2][201]; int main() { int i, j, k, l; for (scanf("%d", &T);T--;){ scanf("%d%d%d%d", &N, &M, &L, &G); for (i=1;i<=N;i++) for (j=1;j<M;j++) scanf("%d", H[i]+j); for (i=1;i<N;i++) for (j=1;j<=M;j++) scanf("%d", V[i]+j); for (i=1;i<=N;i++) for (j=1;j<=M;j++) for (k=0;k<2;k++) for (l=0;l<201;l++) D[i][j][k][l] = G+1; D[1][1][0][0] = D[1][1][1][0] = 0; int ans = 2e9; for (i=1;i<=N;i++) for (j=1;j<=M;j++) for (l=0;l<201;l++) for (k=0;k<2;k++) if (D[i][j][k][l] <= G){ //printf("%d %d %d %d: %d\n", i, j, k, l, D[i][j][k][l]); if (i == N && j == M){ if (ans > l) ans = l; } if (l < 200 && D[i][j][!k][l+1] > D[i][j][k][l]) D[i][j][!k][l+1] = D[i][j][k][l]; if (k){ if (j < M && D[i][j+1][k][l] > D[i][j][k][l]+H[i][j]) D[i][j+1][k][l] = D[i][j][k][l]+H[i][j]; } else{ if (i < N && D[i+1][j][k][l] > D[i][j][k][l]+V[i][j]) D[i+1][j][k][l] = D[i][j][k][l]+V[i][j]; } } if (ans < 2e9) printf("%d\n", (N+M-2)*L+ans); else puts("-1"); } }

저작자표시

'ICPC > 2014 인터넷예선' 카테고리의 다른 글

G. Mutation  (0)	2014.10.08
E. Highway  (0)	2014.10.07
D. 헨리  (0)	2014.10.07
C. 그리드 그래프  (2)	2014.10.07
B. Driving License  (1)	2014.10.07
A. ACM 호텔  (0)	2014.10.07