# Dungeons and Maps - CodinGame | C++ Implementation

The problem is from CodinGame with difficulty level Easy.

# Problem:

You are given `N`

maps for a dungeon. Each map may contain a path to a treasure `T`

, from starting position [ `startRow`

; `startCol`

]. Determine the `index`

of the map which holds the shortest path from the starting position to `T`

, but be careful a map may lead you to a `TRAP`

.

A path is marked on the map with `^`

, `v`

, `<`

, `>`

symbols, each corresponding to **UP**, **DOWN**, **LEFT**, **RIGHT** directions respectively, i.e. each symbol shows you the next cell to move on.

A valid path must start from [ `startRow`

; `startCol`

] and end on `T`

.

The path length is the count of direction symbols plus `1`

, for the `T`

cell.

Read full problem here : Dungeons and Maps

# Solution:

We have different maps and we have to find the which map has the shortest distance to the treasure. In output we will print the index of that map.

Characters can be:

1
2
3
4
5
6
7

. - Empty square
# - Wall
^ - Move UP
v - Move DOWN
< - Move LEFT
> - Move RIGHT
T - The treasure square

When we encounter wall or an empty square, we cannot proceed further. Means the treasure cannot be found in that map.

We will store all maps in a vector. Each row in a map is a string and each map is a vector of strings. Width `w`

and height `h`

of the maps is given. So the vector to store maps is :

1

std::vector< std::vector<std::string> > maps(n, std::vector<std::string>(h));

Here `n`

is the number of maps.

The integer variables `start_row`

and `start_col`

denote starting position on the map.

This is how vector `maps`

will look like -

A `for`

loop will be used to traverse through 2D verctor `maps`

and `while`

loop to traverse through each map.

An integer variable `shortest_distance`

will be initialised with the highest value an integer can store.

1

int shortest_distance = std::numeric_limits<int>::max();

An integer variable `count`

, stores the distance from starting position to the treasure for each map. It is initialised with `0`

, when processing of a map is completed and if the value of `count`

is less than value of `shortest_distance`

, then `shortest_distance`

is updated with the value of `count`

. Means we have a new map whose distance to treasure is the shortest.

For eg., after processing map at index `0`

, the value of count we get is 5 which is less than the value of `shortest_distance`

. So the new value of `shortest_distance`

is 5.

This updating of `shortest_distance`

with new value of `count`

is done at the end. Before that we have to terminate unnecessary processing.

For eg., while processing map at index `1`

, the current value of `count`

is greater than `shortest_distance(=5)`

. So there is no need to process it anymore. It will not give us desired result even if we find treasure in the map. So, we will terminate the processing using `break`

statement.

1
2
3
4

if (count >= shortest_distance) //current map does not have shortest distance, so break
{
break;
}

While moving up and down, the value of row is changed and while moving left and right, the value of column is changed.

So, before processing a map, integer variable `next_row`

is initialised with `start_row`

and `next_col`

is initialised with `start_col`

.

1
2

int next_row = start_row;
int next_col = start_col;

This is how we will move through the map -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

if (maps[i][next_row][next_col] == '^') // Up
{
next_row = next_row - 1;
count++;
}
else if (maps[i][next_row][next_col] == 'v') // Down
{
next_row = next_row + 1;
count++;
}
else if (maps[i][next_row][next_col] == '<') // Left
{
next_col = next_col - 1;
count++;
}
else if (maps[i][next_row][next_col] == '>') // Right
{
next_col = next_col + 1;
count++;
}
else if (maps[i][next_row][next_col] == '.' || maps[i][next_row][next_col] == '#') // empty sqaure or wall
{
break;
}

We will terminate the processing of the map if empty square or wall is encountered.

Successfully reaching the treasure -

We will have to terminate the processing if a loop in formed in a map.

If the value of `next_row`

is less than 0 and greater than and equal to the width of map, then we have to terminate the processing. Similarly, if the value of `next_col`

is less than 0 and greater than and equal to height of the map, then also we have to terminate the processing.

1
2
3
4
5
6
7
8
9
10
11
12

if (next_row == start_row && next_col == start_col) //forms loop, so break
{
break;
}
else if (next_row < 0 || next_row >= width) //exceeding boundary(width)
{
break;
}
else if (next_col < 0 || next_col >= height) //exceeding boundary(height)
{
break;
}

If we found the map with shortest distance to treasure then its index number is updated to an integer variable `index`

. Initially `index`

was initialised with `-1`

.

1
2
3
4
5
6
7
8
9
10

if (maps[i][next_row][next_col] == 'T')//finds treasure
{
count++;
if (shortest_distance > count)
{
index = i;
shortest_distance = count;
}
break;
}

We will stop the processing once we find the treasure.

### C++ Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <iostream>
#include <string>
#include <vector>
#include <limits>
int shortest_path_map_index(std::vector< std::vector<std::string> >& maps, int start_row, int start_col,
int num_maps, int width, int height)
{
int index = -1;
int shortest_distance = std::numeric_limits<int>::max();
for (int i = 0; i < num_maps; ++i)
{
int count = 0;
int next_row = start_row;
int next_col = start_col;
while(1)
{
if (count >= shortest_distance) //current map does not have shortest distance, so break
{
break;
}
if (maps[i][next_row][next_col] == '^') // Up
{
next_row = next_row - 1;
count++;
}
else if (maps[i][next_row][next_col] == 'v') // Down
{
next_row = next_row + 1;
count++;
}
else if (maps[i][next_row][next_col] == '<') // Left
{
next_col = next_col - 1;
count++;
}
else if (maps[i][next_row][next_col] == '>') // Right
{
next_col = next_col + 1;
count++;
}
else if (maps[i][next_row][next_col] == '.' || maps[i][next_row][next_col] == '#') // empty sqaure or wall
{
break;
}
if (next_row == start_row && next_col == start_col)//forms loop, so break
{
break;
}
else if (next_row < 0 || next_row >= width)//exceeding boundary(width)
{
break;
}
else if (next_col < 0 || next_col >= height)//exceeding boundary(height)
{
break;
}
if (maps[i][next_row][next_col] == 'T')//finds treasure
{
count++;
if (shortest_distance > count)
{
index = i;
shortest_distance = count;
}
break;
}
}
}
return index;
}
int main()
{
int w;
int h;
std::cin >> w >> h; std::cin.ignore();
int start_row;
int start_col;
std::cin >> start_row >> start_col; std::cin.ignore();
int n;
std::cin >> n; std::cin.ignore();
std::vector< std::vector<std::string> > maps(n, std::vector<std::string>(h));
for (int i = 0; i < n; i++)
{
std::vector<std::string> map(h);
for (int j = 0; j < h; j++)
{
std::string map_row;
std::getline(std::cin, map_row);
map[j] = map_row;
}
maps[i] = map;
}
int map_index = shortest_path_map_index(maps, start_row, start_col, n, w, h);
if (map_index == -1)
{
std::cout << "TRAP\n";
}
else
{
std::cout << map_index << "\n";
}
}

View this on Github

If you have another solution then please share it in the comments below.

### Other Competitive Programming Problems and Solutions