Problem H
Avoiding Jungle in the Dark
Input: Standard Input

Output: Standard Output

A Pilgrim is all set for a long journey to the Holy land. The journey is long and involves covering dangerous grounds. In particular, he needs to go through two types of land, plain and jungles. It is safe to be located on a plain ground during any hour of the day, but traveling into or staying in the jungle must be avoided during dark hours. Also, the Pilgrim is a human so he must take rests. He can not travel continuously for more than 16 hours; he will need a rest after that. However, he can decide to have a rest anytime he wants, even after getting up from one rest session. Once he decides to take a rest, he must do so for exactly 8 hours.

Given the map of the route, help the Pilgrim to determine the minimum time that would be required to travel from the starting position to the destination.

Input

The first line of input contains a positive integer T<=100. Each of the next T lines contains a string of length at least 2 and at most 1000. The string will always begin with an S and end with a D. The characters in between will be either a ‘.’ Or ‘*’, quotes for clarity.  Here a ‘.’ represents a plain land and ‘*’ a jungle. It takes exactly one hour to travel from one position to the next and the Pilgrim never travels backward. Note that he is always located at the left most position of a particular land and when he travels to the next land, he travels for a full hour to the reach the left most position of the next land. 

Output

For each case of input there will be one line of output. It will first contain the case number followed by the minimum time required to reach the destination. In case it is not possible to reach the destination, output -1. Note that he starts his journey from the position marked S and finishes at D. On the first day of his journey, he is located on S at 6 AM. Dark hours are considered to be the time between 6 PM to 6 AM inclusive.

Sample Input                              Output for Sample Input

Problemsetter: Shamim Hafiz

Special Thanks to: Md. Arifuzzaman Arif

狀態記錄兩點 dp[位置][抵達時間]，然後進行轉移

特別要注意幾點，叢林不能在黑暗中經過，但有可能突然轉成白天。

有可能要連續休息兩次(16小時)，但不用休息三次(24小時) 那是毫無意義的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s", s);
        int n = strlen(s);
        int dp[1024][24], inf;
        int i, j, k;
        memset(dp, 63, sizeof(dp));
        inf = dp[0][0];
        dp[0][6] = 0;
        for(i = 0; i < n; i++) {//where
            for(j = 0; j < 24; j++) {//time
                if(dp[i][j] == inf)
                    continue;
                int night = 0, jungle = 0;
                for(k = 1; k <= 16; k++) {//walk time
                    int time = (j+k)%24;
                    if(time >= 18 || time <= 6)
                            night = 1;
                    else    night = 0, jungle = 0;
                    if(s[i+k] == '*' && night)
                        jungle = 1;
                    if(night && jungle)
                        break;
                    if(s[i+k] != '*') {
                        dp[i+k][(time+8)%24] = min(dp[i+k][(time+8)%24], dp[i][j]+k+8);
                        dp[i+k][(time+16)%24] = min(dp[i+k][(time+16)%24], dp[i][j]+k+16);
                    }
                }
            }
        }
        int ret = inf;
        /*for(j = 0; j < 1; j++, puts("")) {
            printf("%2d:", j);
            for(i = 0; i < n; i++) {
                printf("%2c", s[i]);
            }
        }
        for(j = 0; j < 24; j++, puts("")) {
            printf("%2d:", j);
            for(i = 0; i < n; i++) {
                if(dp[i][j] == inf) printf("##");
                else    printf("%2d", dp[i][j]);
            }
        }*/
        for(i = 0; i < 24; i++)
            ret = min(ret, dp[n-1][i]);
        printf("Case #%d: ", ++cases);
        if(ret == inf)
            puts("-1");
        else
            printf("%d\n", ret-8);
    }
    return 0;
}