IMHO, I think that having S and D in the question really complicates the understanding of the problem.
I still don't understand what is the nature of S and D. Are they plains?
If they are plains, is the question about moving from left of S to left of D, or right of S to right of D?!
So, assuming that we move from left of S to left of D, here is the code:
I assume that 6AM is 0, and therefore 6PM is 12.
Code: Select all
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <ctime>
#include <map>
#include <set>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
#define GI ({int t;scanf("%d",&t);t;})
#define dbg(x) cout << #x << " -> " << x << "\t" << flush;
#define dbge(x) cout << #x << " -> " << x << "\t" << endl;
#define LET(x,a) typeof(a) x(a)
#define FORI(i,a,b) for(LET(i,a);i!=(b);++i)
#define FOR(i,a,b) for(LET(i,a);i < (b);++i)
#define FORZ(i,n) FOR(i,0,n)
#define EACH(i,v) FOR(i,(v).begin(),(v).end())
#define CS c_str()
#define PB push_back
#define SZ size()
#define INF (int)1e9+1
typedef unsigned long long LL;
int arr[1001][25][25];
string str;
int solve(int ind, int time, int howCont)
{
if(ind == str.SZ - 1)
return 0;
int& ret = arr[ind][time][howCont];
if(ret != -1)
return ret;
int x = 0;
ret = INT_MAX;
if(howCont == 16)
if(str[ind] == '.')
{
howCont = 0;
time += 8;
time %= 24;
x += 8;
}
else
return ret = INT_MAX;
if(str[ind] == '*')
if(time >= 12)
return ret = INT_MAX;
/* {
if(str[ind - 1] == '.')
while(time >= 12)
{
howCont = 0;
time += 8;
time %= 24;
x += 8;
}
else
return ret = INT_MAX;
}
*/
int val = solve(ind + 1, (time + 1)%24, howCont + 1);
if(val != INT_MAX)
ret <?= x + 1 + val;
if(str[ind] == '.')
{
x += 8;
time += 8; time %= 24;
val = solve(ind + 1, (time + 1)%24, 1);
if(val != INT_MAX)
ret <?= solve(ind + 1, (time + 1)%24, 1) + x + 1;
x += 8;
time += 8; time %= 24;
val = solve(ind + 1, (time + 1)%24, 1);
if(val != INT_MAX)
ret <?= solve(ind + 1, (time + 1)%24, 1) + x + 1;
x += 8;
time += 8; time %= 24;
val = solve(ind + 1, (time + 1) % 24, 1);
if(val != INT_MAX)
ret <?= solve(ind + 1, (time + 1) % 24, 1) + x + 1;
}
return ret;
}
int main()
{
int nC = GI;
FORZ(nc, nC)
{
cin >> str;
memset(arr, -1, sizeof arr);
str[0] = '.';
int ret = solve(0,0,0);
if(ret == INT_MAX)
ret = -1;
printf("Case #%d: %d\n", nc+1, ret);
}
}