10068 - The Treasure Hunt

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

Moderator: Board moderators

vaibhav
New poster
Posts: 4
Joined: Thu Sep 08, 2005 9:48 pm

treasure hunt code needed!!!!

Post by vaibhav » Thu Sep 08, 2005 10:22 pm

Input

The first line of the input contains two integers R and C (each 20) describing the dimensions of the maze. Then follows R lines of C characters each representing the map of the maze. Each character corresponds to a square block and represents its property ('.' : an empty block, '#' : a blocked block, '*' : a block containing a treasure, 'S' : the starting block, 'T' : the ending block). The next line contains an integer representing the energy required in calories for a walk from a block to an adjacent one. The next line contains pairs of integers (Pi, Ci) representing the pickup and carrying cost in calories for the treasures given in the map from top to bottom and for the same row from left to right. There will be at most 10 treasures in the maze. The input may contain multiple test cases and ends with two zeros for R and C.

Output

For each test case first output the hunt number. In the next line print the minimum energy
required for the hunt. The third line will contain the description of the hunt as a sequence of
characters containing 'N', 'E', 'W', 'S' and 'P'. 'N', 'E', 'W' and 'S' represent a walk to the north, east,
west and south respectively and 'P' means that the treasure is picked up from the current location.
If the hunt is impossible just output the sentence 'The hunt is impossible.' in a line by itself. Each
test case must be followed by a blank line.

INPUT FILE
5 8
#......T
..#*..#.
..######
...*...#
####S.#*
5
10 50 50 100 30 80
10 10
#........*
..#*..#...
..######..
.......#..
####S..##.
.*.#...#..
.......#..
.##.#....#
.*.....#.#
....*..#.T
10
100 400 20 50 150 250 30 70 4 5
0 0

OUTPUT FILE
Hunt #1
The hunt is impossible.
Hunt #2
Minimum energy required = 17539 cal
NWWWNNNEESPNWWSSSEEESSSWSSESPWWWNPWNNENPESEEESEEENENNNNNN
PSSSSSWSSSSE



please help!!!!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Sep 09, 2005 9:34 am

Are you really think, that if you post fragment of one of problem, someone send you solution ?
It's radiculous ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

vaibhav
New poster
Posts: 4
Joined: Thu Sep 08, 2005 9:48 pm

treasure hunt

Post by vaibhav » Fri Sep 09, 2005 2:07 pm

2028 − Treasure Hunt
Latin America − Mexico and Central America − 2000/2001


<AS U MAY SEE THIS IS A PROB OF ACM......IF ANY OF U HAVE SOLUTION OF THIS PLEASE SEND IT TO ME>



In this problem you will be given a map of a rectangular maze with square blocks. From each block you can
move in four directions (N, E, W, S) and you lose some energy for every walk from one block to an adjacent
one. Some blocks of the maze are really blocked − that is you cannot move to those blocks. Some other blocks
contain some treasures that you will have to collect. Each treasure has a particular pickup cost and carrying
cost associated with it. The pickup cost is the energy required to pick up the treasure from the floor and the
carrying cost is the energy required to carry the treasure from one block to an adjacent one. Now given a
starting and ending location in the maze you will have to plan a single walk from the starting location to
collect and carry all the treasures to the ending location at the expense of minimum energy.
Input
The first line of the input contains two integers R and C (each < 21) describing the dimensions of the maze.
Then follows R lines of C characters each representing the map of the maze. Each character corresponds to a
square block and represents its property ('.' : an empty block, '#' : a blocked block, '*' : a block containing a
treasure, 'S' : the starting block, 'T' : the ending block). The next line contains an integer representing the
energy required in calories for a walk from a block to an adjacent one.
The next line contains pairs of integers (Pi, Ci) representing the pickup and carrying cost in calories for the
treasures given in the map from top to bottom and for the same row from left to right. There will be at most 10
treasures in the maze. The input may contain several test cases and ends with two zeros for R and C.
Output
For each test case first output the hunt number. In the next line print the minimum energy required for the
hunt. The third line will contain the description of the hunt as a sequence of characters containing 'N', 'E', 'W',
'S' and 'P'. 'N', 'E', 'W' and 'S' represent a walk to the north, east, west and south respectively and 'P' means that
the treasure is picked up from the current location. If the hunt is impossible just output the sentence 'The hunt
is impossible.' in a line by itself. Each test case must be followed by a blank line.
Sample Input
5 8
#......T
..#*..#.
..######
...*...#
####S.#*
5
10 50 50 100 30 80
10 10
#........*
..#*..#...
..######..
.......#..
####S..##.
.*.#...#..
.......#..
.##.#....#
.*.....#.#
2028 − Treasure Hunt 1/2



plz help me.....if u ve solution of this do send it to me

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Fri Sep 09, 2005 2:37 pm

1. This is not the right place.
2. Don't ever ask someone to send his solution to him.
(Because sending you the solution won't be helping you.)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Sep 09, 2005 3:17 pm

The problem looks to me same as http://acm.uva.es/p/v100/10068.html Try searching posts about that problem.

neo_trax
New poster
Posts: 1
Joined: Fri Sep 09, 2005 9:21 pm

solution

Post by neo_trax » Fri Sep 09, 2005 11:10 pm

Hello Vaibhav
I started solving this problem after u post this message.I m trying it and if I solve it i will mail u the solution.I hope till some one else who has the solution will mail u.Till then try solving yourself........

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Hi

Post by temper_3243 » Sat Sep 10, 2005 5:32 am

where is the problem from ? original source. Can you give it please ?

Well the technique of solving these problems is a BFS or a queue and expanding all states from the initial position. It can get really large. But then you can reduce the states by using an approximation function *depending on the situation * . You need to study AI if you want to continue in this theory for long time. Only for problems lookup on A* or IDA* or one of those search algorithms with a state function which can help you reduce the number of states.

Some of these techniques is used in 15-puzzle but sometimes it fails to get good solutions fast enough.

Hope this helps.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Re: Hi

Post by Observer » Sat Sep 10, 2005 9:30 am

temper_3243 wrote:where is the problem from ? original source. Can you give it please ?
ACM Q10068 Treasure Hunt

Both BFS and backtracking works well in this task.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

vaibhav
New poster
Posts: 4
Joined: Thu Sep 08, 2005 9:48 pm

Post by vaibhav » Fri Sep 16, 2005 1:14 pm

Can u give me the code for this problem........PLZ........

vaibhav
New poster
Posts: 4
Joined: Thu Sep 08, 2005 9:48 pm

Post by vaibhav » Fri Sep 16, 2005 1:15 pm

Can u give me the code for this problem........PLZ........
Mail me at vikram.exe@gmail.com

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Wed Sep 28, 2005 1:57 pm

Hi!! I want to know some hints to solve this problem.
I see the problem has a problem of shortest path but repiting nodes, in the sample input they repeat some nodes in the path, please help me

Thanks in advance
keep posting

Diablos
New poster
Posts: 5
Joined: Thu Oct 05, 2006 4:58 pm
Location: Egypt
Contact:

10068 - WA

Post by Diablos » Wed Oct 11, 2006 7:35 pm

Code: Select all

#include <string>
#include <iostream>
#include <climits>
#include <string.h>
#include <queue>
#include <string>
using namespace std;

#define isNum(a) (a >= '0' && a <= ';')

#ifndef ONLINE_JUDGE
	#include <fstream>
	#define cin in
	ifstream in("10068.in");
#endif

struct Treasure
{
	int Carry, pickup, xLoc, yLoc;
	Treasure(int x, int y) : xLoc(x), yLoc(y) {}
	Treasure(){}
} treasures[12];
int nTreasures;

struct Link
{
	int Len;
	string Way;
	Link() { Len = INT_MAX; }
	void MakeLink(int l, string p)
	{
		Len = l;
		Way = p;
	}
} Graph[12][12] ;
char Floor[21][21];
bool FloorPath[20][20];
int Height, Width;
int Cost;
int memory[1024][12];
int path[12][1024];



void init()
{
	nTreasures = 2;
	memset(Floor, 0, 400);
	memset(memory, 0xFF, 1024*10*sizeof(memory[0][0]));
	for(int i=0; i<12; i++)
		for(int j=0; j<12; j++)
			Graph[i][j] = Link();
}

struct Flood
{
	int x, y;
	unsigned int tillNow;
	string p;
	Flood(int X, int Y, int W, string _p) : x(X), y(Y), tillNow(W), p(_p) {}
};

void FloodFill(short start, short x, short y)
{
	queue<Flood> s;
	s.push( Flood(x, y, 0, "") );
	while(!s.empty())
	{
		Flood f = s.front();
		s.pop();
		
		if(f.x < 0 || f.y < 0 || f.x >= Width || f.y >= Height)
			continue;
		if(Floor[f.y][f.x] == '#' || FloorPath[f.y][f.x]) 
			continue;
		FloorPath[f.y][f.x] = true;

		if( isNum(Floor[f.y][f.x]) ) 
			Graph[start][ Floor[f.y][f.x] - '0' ].MakeLink(f.tillNow, f.p);

		s.push( Flood(f.x, f.y-1  , f.tillNow+1, f.p+'N') );
		s.push( Flood(f.x+1, f.y  , f.tillNow+1, f.p+'E') );
		s.push( Flood(f.x-1, f.y  , f.tillNow+1, f.p+'W') );
		s.push( Flood(f.x, f.y+1  , f.tillNow+1, f.p+'S') );
	}	
}

void BuildGraph()
{
	int i;
	for(i=0; i<nTreasures; i++)
	{
		memset( FloorPath, 0, 20*20*sizeof(FloorPath[0][0]) );
		FloodFill(i, treasures[i].xLoc, treasures[i].yLoc);
	}
}
int walk(int state, int Start, int CostFactor)
{
	if(memory[state][Start] > 0)
		return memory[state][Start];
	int minCost = INT_MAX,i;

	if( state+1 == (1<<(nTreasures-2)) )
	{
		path[Start][state] = 1;
		return Graph[Start][1].Len * CostFactor;
	}

	for(i=2; i<nTreasures; i++)
	{
		if( state & (1<<(i-2)) )
			continue;
		int newState = state | (1<<(i-2));
		int with = walk(newState, i, CostFactor+treasures[i].Carry);
		int step = Graph[Start][i].Len * CostFactor;
		if(with + step + treasures[i].pickup < minCost)
		{
			minCost = with + step + treasures[i].pickup;
			path[Start][state] = i;
		}
	}
	return memory[state][Start] = minCost;
}

void main()
{
	cin >> Height >> Width;
	int Case = 1;
	while(Height != 0 || Width != 0)
	{
		init();
		int i,j;
		for(i=0; i<Height; i++)
			for(j=0; j<Width;j++)
			{
				cin >> Floor[i][j];
				if(Floor[i][j] == '*')
				{
					Floor[i][j] = nTreasures + '0';
					treasures[nTreasures++] = Treasure(j, i);
				}
				else if(Floor[i][j] == 'S')
				{
					Floor[i][j] = '0';
					treasures[0] = Treasure(j,i);
				}
				else if(Floor[i][j] == 'T')
				{
					Floor[i][j] = '1';
					treasures[1] = Treasure(j,i);
				}
			}
		BuildGraph();
		cin >> Cost;
		for(i=2; i<nTreasures; i++)
			cin >> treasures[i].pickup >> treasures[i].Carry;
		cout << "Hunt #" << Case++ << endl;
		bool feasible=true;
		for(i=0; i<nTreasures;i++)
			if(Graph[0][i].Len == INT_MAX)
				feasible = false;
		if(feasible)
		{
			cout << "Minimum energy required = " << walk(0, 0, Cost) << " cal" << endl;
			int state = 0;
			for(i=0; i!=1; )
			{
				int newI = path[i][state];
				cout << Graph[ i ][ newI ].Way;
				i = newI;
				state = state | ( 1<<(i-2) );
				if(newI != 1)
					cout << "P";
			} 
		}
		else cout << "The hunt is impossible.";
		cout << endl << endl;
		cin >> Height >> Width; 
	}
}
This is the code that I made to The Treasure Hunting problem, I tested it many many many times, giving the right output

but the judge is giving me WA

please, heeeeeeeeeeeeeeeeeeeeeeelp
Mustafa M. Mohie,
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com

Diablos
New poster
Posts: 5
Joined: Thu Oct 05, 2006 4:58 pm
Location: Egypt
Contact:

Post by Diablos » Fri Oct 13, 2006 5:49 pm

is it about the order of the movement ??!!!!!!
which is first and what's the order please ???

North, East, West, South ?
Mustafa M. Mohie,
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com

caio
New poster
Posts: 1
Joined: Fri Nov 24, 2006 5:21 am

Post by caio » Fri Nov 24, 2006 5:23 am

It's not working under linux using gcc!

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Some clarifications needed

Post by ranban282 » Sun Feb 25, 2007 2:31 pm

Hi,
I have 2 doubts:
1. Can the guy visit a spot he has already visited?
2. When he walks without any treasures, he takes energy required in calories for a walk from a block to an adjacent one * distance. When carrying treasures, is this cost added?
3. If a guy passes through a point which contains a treasure, does he have to pick it up, or can he leave it?

Post Reply

Return to “Volume 100 (10000-10099)”