10068  The Treasure Hunt
Moderator: Board moderators
treasure hunt code needed!!!!
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!!!!
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!!!!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Are you really think, that if you post fragment of one of problem, someone send you solution ?
It's radiculous ...
Best regards
DM
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)
Born from ashes  restarting counter of problems (800+ solved problems)
treasure hunt
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
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
The problem looks to me same as http://acm.uva.es/p/v100/10068.html Try searching posts about that problem.
solution
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........
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........

 Experienced poster
 Posts: 105
 Joined: Wed May 25, 2005 7:23 am
Hi
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 15puzzle but sometimes it fails to get good solutions fast enough.
Hope this helps.
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 15puzzle but sometimes it fails to get good solutions fast enough.
Hope this helps.
Re: Hi
ACM Q10068 Treasure Hunttemper_3243 wrote:where is the problem from ? original source. Can you give it please ?
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Can u give me the code for this problem........PLZ........
Mail me at vikram.exe@gmail.com
Mail me at vikram.exe@gmail.com

 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela
10068  WA
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.y1 , f.tillNow+1, f.p+'N') );
s.push( Flood(f.x+1, f.y , f.tillNow+1, f.p+'E') );
s.push( Flood(f.x1, 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<<(nTreasures2)) )
{
path[Start][state] = 1;
return Graph[Start][1].Len * CostFactor;
}
for(i=2; i<nTreasures; i++)
{
if( state & (1<<(i2)) )
continue;
int newState = state  (1<<(i2));
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<<(i2) );
if(newI != 1)
cout << "P";
}
}
else cout << "The hunt is impossible.";
cout << endl << endl;
cin >> Height >> Width;
}
}
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
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com
is it about the order of the movement ??!!!!!!
which is first and what's the order please ???
North, East, West, South ?
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
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com
Some clarifications needed
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?
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?