[UVA][DP] 11617 - An Odd Love
| D. An Odd Love |
Context
Spring has arrived and our friend Pepito has fallen in love. But he is not sure if she also loves him, so he decides to ask the daisies. He takes a daisy and alternately speaks the phrases "She loves me" and "She loves me not", while picking one petal off the flower for each phrase. The phrase corresponding to the last petal tells him whether his love is reciprocated or not.
We want to help Pepito to always obtain the answer "She loves me". Therefore, we will make sure that all the daisies have an odd number of petals, by picking one petal off the flowers with an even number.
The Problem
We have a rectangular field of daisies, whose width is W and height H. There is a daisy in each position of this field (w, h), with w= 1, 2, ..., W, and h= 1, 2, ..., H. We have patiently counted the number of petals of each daisy, P[w, h].
Starting from the upper-left corner of the field --i.e., from position (1, 1)-- you have to pass through all positions of daisies with an even number of petals. If your current position is (w, h), you can only do three movements: go down (h+1), go left (w-1) and go right (w+1).
Your task is to compute the minimum number of movements necessary to pass through all positions with an even number of petals.
A sample case with W = 5 and H = 3. The solution is 11. This sample corresponds
to the first case in the sample input.
The Input
The first line of the input contains an integer indicating the number of test cases.
For each test case, the first line contains two integers, W and H, separated by a blank space. Then, there are H lines. Each line consists of W digits (between 1 and 9) indicating the number of petals of the corresponding daisy.
The Output
For each test case, the output should contain the minimum number of movements of the corresponding case.
Sample Input
5 5 3 54578 36329 75241 9 1 759456785 2 2 22 22 6 6 777777 772777 777777 777727 727777 777777 7 7 1811181 1118811 1881111 8111111 1188181 1881181 1111111
Sample Output
11 7 3 11 24
OMP'09
Facultad de Informatica
Universidad de Murcia (SPAIN)
現在要把所有偶數的花朵摘掉，求移動最少步數。
一開始在地圖的左上角，接著只能左右移動和往下移動。
題目解法：
無須對所有下一行的所有位置進行狀態轉移，只要考慮停留在左端點還是右端點即可。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char g[1024][1024];
int main() {
int testcase;
int n, m;
int i, j, k;
int L[1024], R[1024], C[1024];
int dp[1024][2];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &m, &n);
int N = 0;
for(i = 0; i < n; i++) {
scanf("%s", g[i]);
int l, r;
l = r = -1;
for(j = 0; j < m; j++) {
if((g[i][j] - '0')%2)
continue;
if(l == -1)
l = j;
r = j;
}
if(l != -1) {
L[N] = l;
R[N] = r;
C[N] = i;
N++;
}
}
memset(dp, 0x7f, sizeof(dp));
if(N == 0) {
puts("0");
continue;
}
int ret = C[N-1];
for(i = 0; i < N; i++) {
int pos[2], cost[2];
if(i == 0)
pos[0] = pos[1] = cost[0] = cost[1] = 0;
else {
pos[0] = L[i-1];
pos[1] = R[i-1];
cost[0] = dp[i-1][0];
cost[1] = dp[i-1][1];
}
int c1, c2;
c1 = abs(pos[0] - R[i]) + R[i] - L[i] + cost[0];
c2 = abs(pos[1] - R[i]) + R[i] - L[i] + cost[1];
dp[i][0] = min(c1, c2);
c1 = abs(pos[0] - L[i]) + R[i] - L[i] + cost[0];
c2 = abs(pos[1] - L[i]) + R[i] - L[i] + cost[1];
dp[i][1] = min(c1, c2);
}
ret += min(dp[N-1][0], dp[N-1][1]);
printf("%d\n", ret);
}
return 0;
}