sai
BAN USERengineer
- 1of 1 vote
AnswersAbstract
- sai in United States for engineer
We are planning an orienteering game.
The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.
However, the players have to pass all the checkpoints (@) on the map.
An orienteering map is to be given in the following format.
########
#@....G#
##.##@##
#..@..S#
#@.....#
########
In this problem, an orienteering map is to be given.
Calculate the minimum distance from the start to the goal with passing all the checkpoints.
Specification
* A map consists of 5 characters as following.
You can assume that the map does not contain any invalid characters and
the map has exactly one start symbol 'S' and exactly one goal symbol 'G'.
* 'S' means the orienteering start.
* 'G' means the orienteering goal.
* '@' means an orienteering checkpoint.
* '.' means an opened-block that players can pass.
* '#' means a closed-block that players cannot pass.
* It is allowed to move only by one step vertically or horizontally (up, down, left, or right) to the
next block.
Other types of movements, such as moving diagonally (left up, right up, left down and right down)
and skipping one or more blocks, are NOT permitted.
* You MUST NOT get out of the map.
* Distance is to be defined as the number of movements to the different blocks.
* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.
* You can assume that parameters satisfy following conditions.
* 1 <= width <= 100
* 1 <= height <= 100
* The maximum number of checkpoints is 18.
* Return -1 if given arguments do not satisfy specifications, or players cannot arrive at the goal
from the start by passing all the checkpoints.
1/6
Examination 1
*You can choose Java or C++| Report Duplicate | Flag | PURGE
job tessio job tessio job tessio job tessio C++
could not get output,,,,
- sai November 13, 2014class orienting
{
public:
void main();
//height of map
const int mapHeight =6;
//width of map
const int mapWidth = 8;
// representation of map
char map[mapHeight][mapWidth + 1] =
{
"########",
"#@....G#",
"##.##@##",
"#..@..S#",
"#@.....#",
"########",
};
const char closeblock = '#';
const char openblock= '.';
const char checkpoint = '@';
class orienting::main(start.x,start.y)
{
public:
int X;
int Y;
orienting(int x = 0, int y = 0) { X = x, Y = y; }
orienting(const orientinggame &orientinggame)
{
X = orienting.X;// orienting position of the move
Y = orienting.Y;//orienting position of the move
}
};
orienting.start(4,7);
orienting.goal(2, 7);
void displaymap()
{
for (int Y = 0; Y < mapHeight; Y++)
{
for(int X=0;x<mapWidth;X++)
{
cout<<"The shortest path from start S(2,7) to goal G(4,7) is"<<map[Y][X]);
}
}
printf("\n");
}
bool Solve(int X, int Y)
{
// stop the searching progress in another direction
map[Y][X] =closeblock;
//progressive update of blocked positions that user cannot pass
displaymap();
sleep(50);
// move to the position if it is shortest path
map[y][x]=openblock;
displaymap();
// Make the move (if it's wrong, we will backtrack later.
map[Y][X] = checkpoint;
// for progressive update of map
displaymap();
Sleep(50);
// Check if we have reached our goal.
if (X == goal.X && Y == goal.Y)
{
return true;
}
// Recursively searching for our goal.
if (X > 0 && map[Y][X - 1] ==openblock && Solve(X - 1, Y))
{
return true;
}
if (X < mapWidth && map[Y][X + 1] ==openblock && Solve(X + 1, Y))
{
return true;
}
if (Y > 0 && map[Y - 1][X] == openblock && Solve(X, Y - 1))
{
return true;
}
if (Y < mapHeight && map[Y + 1][X] ==openblock && Solve(X, Y + 1))
{
return true;
}
// Otherwise we need to backtrack and find another solution.
map[Y][X] =openblock;
// for progressive update
display();
Sleep(50);
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
orienting o;
o.main(orienting.start,&orienting.goal);
if (Solve(start.X, start.Y))
{
displaymap();
}
else
{
printf("map does not exists\n");
}
return 0;
}