## 11545 - Avoiding Jungle in the Dark

Moderator: Board moderators

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

### 11545 - Avoiding Jungle in the Dark

I don't why my code gives WA!
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);
}
}
``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Re: 11545 Avoiding Jungle in the Dark

Your understanding of left of S to left of D is correct. That description was there to remove ambiguity of border regions between jungle and plain lands. It was implied that, you are strictly located on one land and one hour later, you will be located in the next, having no concern about the intermediate journey.

You start on S at 6 AM, so it was safe to be located there during dark hours, hence it can be considered a plain(safe) land. D is the destination and you can reach there during dark hours also, although this wasn't explicitly mentioned in the problem statement.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

### Re: 11545 Avoiding Jungle in the Dark

shamim wrote:Your understanding of left of S to left of D is correct. That description was there to remove ambiguity of border regions between jungle and plain lands. It was implied that, you are strictly located on one land and one hour later, you will be located in the next, having no concern about the intermediate journey.
You start on S at 6 AM, so it was safe to be located there during dark hours, hence it can be considered a plain(safe) land. D is the destination and you can reach there during dark hours also, although this wasn't explicitly mentioned in the problem statement.
I think my code, satisfies all the conditions you said.
Can you give me some test cases?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Re: 11545 Avoiding Jungle in the Dark

I didn't look into your code thoroughly, but check to see if you are handling "sleeping inside danger zone" properly.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

### Re: 11545 Avoiding Jungle in the Dark

shamim wrote:I didn't look into your code thoroughly, but check to see if you are handling "sleeping inside danger zone" properly.
Yeah, you are right, I don't rest inside "danger zone" at all, though it is permitted to rest there during the day! thanks!
Anyway, even after including that, my code gives WA!

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)
return ret = INT_MAX;
if(str[ind] == '*')
if(time >= 12)
return ret = INT_MAX;
int val = solve(ind + 1, (time + 1)%24, howCont + 1);
if(val != INT_MAX)
ret <?= x + 1 + val;
FORZ(i, 8)//Just added more than enough rest!
{
if(str[ind] == '*' && time >= 12)
break;
x += 8;
time += 8; time %= 24;
if(str[ind] == '*' && time >= 12)
break;
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);
}
}
``````
If anyone, can give some random test case or find what is error in the code, I will be happy!

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

### Re: 11545 Avoiding Jungle in the Dark

Code: Select all

``````9
S.**....*****D
S.****..*****D
S*.**.*.*****D
S**.....*****D
S**...*.*****D
S**.*...*****D
S**.*.*.*****D
S**.***.*****D
S****.*.*****D
``````
According to my AC program all answers are -1. Your code outputs 29 on all of them. You can get the expected answers for your own input sets on my homepage, http://www.uvatoolkit.com.
For help with problems, visit http://www.uvatoolkit.com/

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11545 Avoiding Jungle in the Dark

Some input for anyone having trouble with the problem:

Code: Select all

``````11
S........*****.*****D
S.........****...*****......*..***..**D
S...***.......**.....***....***...**.......****D
S........**..****..........***........*****......*****....**D
S....****.....**..****D
S........*****...***........*****....**..........****.......*.***.........**.***D
S.........**......*..........*.**..****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S..****......*****.........*****.***.......****.......**......*****...*..........***....***D
S.......*..**......***D
S......*****.****D
``````
output:

Code: Select all

``````Case #1: 36
Case #2: 102
Case #3: 103
Case #4: 108
Case #5: 54
Case #6: 152
Case #7: 79
Case #8: 221
Case #9: 179
Case #10: 54
Case #11: 33
``````

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

### Re: 11545 Avoiding Jungle in the Dark

Hello,
Here the problem says the person can take rest any time after he completed one rest session but again it says that one can rest exactly 8 hours... I can't understand

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Re: 11545 Avoiding Jungle in the Dark

The two statements describe two different situations without conflicting with each other.

the person can take rest any time after he completed one rest session

This means, after taking a rest for 8 hours, he can decide to take another one for 8 hours.

One can rest exactly 8 hours

This means, he has to rest for exactly eight hours in one rest session, that is he can't rest for 7 hours or 9 hours or any other value for that matter.

I hope I could clarify the statements.

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

### Re: 11545 Avoiding Jungle in the Dark

thanks shamim vai.
I got it.......

bourne
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

### Re: 11545 - Avoiding Jungle in the Dark

I get correct answer for every test case on this forum still OJ gives me WA. I am not able to find the bug.

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
using namespace std;
#define INF 200000000

char a[1005];
int n,dp[1005][24][18];
int solve(int pos,int t,int h)
{
if(pos==n) return 0;
int& res=dp[pos][t][h];
if(res!=-1) return res;
res=INF;
int tt;

//resting
bool ok=1;
if(a[pos]=='*'){
for(int i=t;i<t+8;i++)
{
tt=i%24;
if(tt<=6 || tt>=18){
ok=0;
break;
}
}
}
if(ok) res=min(res,8+solve(pos,(t+8)%24,0));

//move at night
if(a[pos]=='*' && h<16 && t>6 && t<18) res=min(res,1+solve(pos+1,(t+1)%24,h+1));

//move during day
if(a[pos]!='*' && h<16) res=min(res,1+solve(pos+1,(t+1)%24,h+1));

return res;
}
int main()
{
int t;
cin>>t;
for(int kase=1;kase<=t;kase++)
{
cin>>a;
n=strlen(a);
memset(dp,-1,sizeof(dp));
int res=solve(0,6,0);
printf("Case #%d: ",kase);
if(res>=INF)
printf("-1\n");
else
printf("%d\n",res-1);
}
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11545 - Avoiding Jungle in the Dark

Try the cases.

Input:

Code: Select all

``````2
S**..*.**.......D
S*.*.*.*.*......D``````
Output:

Code: Select all

``````Case #1: 16
Case #2: 16``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

stormbind
New poster
Posts: 1
Joined: Sat Aug 07, 2010 2:54 am

### Re: 11545 - Avoiding Jungle in the Dark

Hello,

I'm having big troubles with this problem. I can't find a testcase where it fails. I've tested a lot of them, I post them here (using the AC homepage of greve you can find output).

Code: Select all

``````118
SD
S*D
S.D
S.**....*****D
S.****..*****D
S*.**.*.*****D
S**.....*****D
S**...*.*****D
S**.*...*****D
S**.*.*.*****D
S**.***.*****D
S****.*.*****D
S........*****.*****D
S.........****...*****......*..***..**D
S...***.......**.....***....***...**.......****D
S........**..****..........***........*****......*****....**D
S....****.....**..****D
S........*****...***........*****....**..........****.......*.***.........**.***D
S.........**......*..........*.**..****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S..****......*****.........*****.***.......****.......**......*****...*..........***....***D
S.......*..**......***D
S......*****.****D
S**..*.**.......D
S*.*.*.*.*......D
S****D
S*****D
S******D
S*******D
S********D
S*********D
S**********D
S***********D
S************D
S*************D
S**************D
S***************D
S****************D
S*****************D
S.*.*.*.*D
S.*.*.*.*.*D
S.*.*.*.*.*.*D
S.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.D
S*.*.*.*.*.D
S*.*.*.*.*.*.D
S*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.D
S.*.*.*.*.*.D
S.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*D
S*.*.*.*.*.*D
S*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*D
S..*D
S...*D
S....*D
S.....*D
S......*D
S.......*D
S........*D
S.........*D
S..........*D
S...........*D
S............*D
S.............*D
S..............*D
S...............*D
S................*D
S...........*...........*D
S...........*...........*...........*D
S...........*............*D
S...........*...........*............*D
S......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S***********.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.**D
``````

Code: Select all

``````#include <stdio.h>
#include <queue>

using namespace std;

struct state
{
unsigned char hour;
int nhours;
unsigned char travelled;
short int pos;
};

bool operator<(const state &e1, const state &e2)
{
if(e1.nhours > e2.nhours) return true;
if(e1.nhours < e2.nhours) return false;
if(e1.pos < e2.pos) return true;
if(e1.pos > e2.pos) return false;
if(e1.travelled > e2.travelled) return true;
if(e1.travelled < e2.travelled) return false;
return e1.hour < e2.hour;
}

char buff[1<<20];

int main()
{
int ncases;
scanf("%d",&ncases);
for(int c=1;c<=ncases;c++) {
scanf("%s",buff);
buff[0] = '.';
priority_queue<state> q;
state start;
start.hour = 6;
start.pos = 0;
start.nhours = 0;
unsigned hash[25][17][1003];
memset(hash,-1,sizeof(hash));
q.push(start);
bool found = false;
while(!q.empty()) {
state cur = q.top();
q.pop();

if(buff[cur.pos] == 'D') {
printf("Case #%d: %d\n",c,cur.nhours);
found = true;
break;
}

if(buff[cur.pos] == '*') {
if((cur.hour > 6) && (cur.hour < 18)) {
if((((cur.hour + 8)%24) > 6) && (((cur.hour + 8)%24) < 18)) {
state sleep;
sleep.hour = (cur.hour + 8)%24;
sleep.pos = cur.pos;
sleep.travelled = 0;
sleep.nhours = cur.nhours + 8;
if(hash[sleep.hour][sleep.travelled][sleep.pos] > sleep.nhours) {
hash[sleep.hour][sleep.travelled][sleep.pos] = sleep.nhours;
q.push(sleep);
}
}
if(cur.travelled < 16) {
state jungle;
jungle.hour = cur.hour + 1;
jungle.pos = cur.pos + 1;
jungle.travelled = cur.travelled + 1;
jungle.nhours = cur.nhours + 1;
if(hash[jungle.hour][jungle.travelled][jungle.pos] > jungle.nhours) {
hash[jungle.hour][jungle.travelled][jungle.pos] = jungle.nhours;
q.push(jungle);
}
}
}
} else {
state sleep;
sleep.hour = (cur.hour + 8)%24;
sleep.pos = cur.pos;
sleep.travelled = 0;
sleep.nhours = cur.nhours + 8;
if(hash[sleep.hour][sleep.travelled][sleep.pos] > sleep.nhours) {
hash[sleep.hour][sleep.travelled][sleep.pos] = sleep.nhours;
q.push(sleep);
}

if(cur.travelled < 16) {
state plane;
plane.hour = (cur.hour + 1)%24;
plane.pos = cur.pos + 1;
plane.nhours = cur.nhours + 1;
plane.travelled = cur.travelled + 1;
if(hash[plane.hour][plane.travelled][plane.pos] > plane.nhours) {
hash[plane.hour][plane.travelled][plane.pos] = plane.nhours;
q.push(plane);
}
}
}
}
if(!found) printf("Case #%d: -1\n",c);
}
return 0;
}
``````
Thank you very much to help me finding a wrong output of my code.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am