10068 - The Treasure Hunt

[vaibhav]

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]

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

Best regards
DM

[vaibhav]

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]

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]

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

[neo_trax]

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]

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]

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.

[vaibhav]

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

[vaibhav]

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

[Ghust_omega]

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]

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

[Diablos]

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

North, East, West, South ?

[caio]

It's not working under linux using gcc!

[ranban282]

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?