11545 - Avoiding Jungle in the Dark

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11545 - Avoiding Jungle in the Dark

Post by srrajesh » Sat Oct 25, 2008 6:56 pm

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);
    }
}

User avatar
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

Post by shamim » Sat Oct 25, 2008 7:15 pm

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

Post by srrajesh » Sat Oct 25, 2008 7:38 pm

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.
Thanks for your reply.
I think my code, satisfies all the conditions you said.
Can you give me some test cases?

User avatar
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

Post by shamim » Sun Oct 26, 2008 7:46 am

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

Post by srrajesh » Sun Oct 26, 2008 11:07 am

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!
Thanks, in advance.

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

Re: 11545 Avoiding Jungle in the Dark

Post by greve » Sun Oct 26, 2008 12:32 pm

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

Post by Leonid » Tue Oct 28, 2008 2:11 pm

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

Post by rhsumon » Fri Nov 07, 2008 6:38 am

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

User avatar
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

Post by shamim » Fri Nov 07, 2008 6:45 am

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

Post by rhsumon » Fri Nov 07, 2008 5:10 pm

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

Post by bourne » Fri Dec 26, 2008 2:37 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 11545 - Avoiding Jungle in the Dark

Post by Jan » Tue Dec 30, 2008 12:45 pm

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

Post by stormbind » Sun Aug 08, 2010 5:58 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11545 - Avoiding Jungle in the Dark

Post by Shafaet_du » Wed Jul 13, 2011 6:44 pm

consider consecutive asterix's+1 as the distance between the node before 1st asterix and the node after the last asterix. Dont travel at night if distance between two node is greater than 1. Run a bfs with 3states.(current pos,current time,current energy)

Post Reply

Return to “Volume 115 (11500-11599)”