Back
Close
Employers: discover CodinGame for tech hiring
EVENTS
UPCOMINGPAST
SOLO
PUZZLESCODE GOLFOPTIMIZATION
MULTI
LEADERBOARDSCLASH OF CODEBOT PROGRAMMINGCODING ESCAPE
COMMUNITY
CONTRIBUTIONSLEARNDISCORDFORUMLIVE STREAMS

A Man with a Plan

Statement

 Goal

You're a peasant, but you've got enough of this life. You want to be famous, rich, and live in a castle… And you have a plan to reach this objective: You heard that the king would be extremely generous with the hero who would fulfill a certain act of bravery in his name. You must be this hero! You gonna leave your house, cross the realm, achieve the king's quest, and then go to the castle to get your due. So much to do to make your dream come true! So you want to plan your journey perfectly to avoid any waste of time.

You procured a map of the realm and, looking at it, you notice there are four kinds of grounds you might be confronted with: Firstly, flat and peaceful grasslands, that you can cross in two days. Secondly, water points. You do not know how to swim, but there will always be a fisher to make you pass through in two days on his boat. Thirdly, mountains. You will have to climb to pass them, but you are a strong man and you think that will take just four days. And finally, swamps... A real hell, that will retain you six days! You also notice the existence of ravines, but you decide to consider them as impassable because you have vertigo.

You continue your study of the map with the points of interest existing in the realm.

There is of course the king's castle, your final goal, which is pretty well guarded. Pass by there before you finish your quest will make you waste one day convincing the guards you are not a thief.

You note the presence of two shops that could potentially be helpful. A blacksmith, who can sell you an armor and a sword that will permit you to accomplish any act of bravery twice as fast. And a stable, where you can buy a horse to travel twice as fast, even on water since the horse can pull the boat. But you want to be sure those purchases will serve your quest, because you are aware that you will not be able to climb a mountain with your horse, or to cross a water point without your armor rusting. And it's absolutely out of question to abandon them once purchased. Moreover, you are very bad at negotiating, while the blacksmith and the breeder are certainly real sharks. You can be sure that if you enter in one of those stores, you will spend one day arguing, to finally surrender and buy something. You also know from their reputation that these two men really love their respective work, and would not hesitate to retain you one day to verify you are taking good care of your purchases, if you pass back by their workshops.

There's also the house of a crazy wizard, who teleports anyone he sees to the closest point of interest. That can be useful, or a total mess. You have to study carefully where the old man will send you and then use his "services" wisely, or not at all. All the more that you will need one day to recover after the sudden change of environment...

You now observe three special places: The lair of an awful dragon, a cavern known to hide a fantastic treasure, and a dungeon where is imprisoned a princess member of the royal family. You know that the king's quest only concern one of those, but you do not exclude the possibility to cross the other two if that can save you some time. Since each of those spots is extremely dangerous and populated with enemies, it will take you four days to pass through one of them. But once the cleansing done, passing there again will only take one day. But not less, even with a horse, because of the tourists that will inevitably come to admire the places of your feats.

Finally, you add your house to the map. You know that your mother will not let you leave so easily, she can be a little clingy. You will have to devote a full day to convince her to let you go, and another day each time you return home... But, hey! She's your mom!

With the map of the realm in your possession, and knowing the objective of the king's quest, can you say how many days your quest will take you at least?

The names of the puzzle and of the tests are all metal song titles! Listen to the playlist here:
https://www.youtube.com/playlist?list=PLbo9xrKG9gGa8yMeLBbst0GEpeBk2BPCT

Art by Florent Llamas:
https://www.deviantart.com/florentllamas
Input
First line: W, H and N, three integers, respectively the width and the height of the realm, and the number of points of interest existing in the realm.

Second line: O, a string, the objective of the king's quest.

Next H lines: A string of length W with each char representing a piece of land of the realm, among:
- G for a grassland,
- W for a water point,
- M for a mountain,
- S for a swamp,
- R for a ravine,
- I for a point of interest.

Next N lines: k, x and y, a string and two integers, respectively the kind and the coordinates of a point of interest. With k among:
- HOUSE,
- CASTLE,
- BLACKSMITH,
- STABLE,
- WIZARD,
- PRINCESS,
- DRAGON,
- TREASURE.
Output
An integer D, the minimum number of days that your quest will take.
Constraints
The (0, 0) coordinates correspond to the top-left corner of the realm.

Each piece of land is directly connected to its eight neighbors.

The wizard uses Manhattan distance.

3 <= W, H <= 20
3 <= N <= 8
0 <= x < W
0 <= y < H
0 < D < 100
Example
Input
5 5 3
PRINCESS
GGGGI
GGGGG
GGIGG
GGGGG
IGGGG
HOUSE 0 4
CASTLE 4 0
PRINCESS 2 2
Output
9
Tags
Pathfinding, Reading the statement
Difficulty
Hard
Test cases
Run to the Hills Test
Input
5 5 3 PRINCESS GGGGI GGGGG GGIGG GGGGG IGGGG HOUSE 0 4 CASTLE 4 0 PRINCESS 2 2
Output
9
Run to the Hills Validator
Input
5 5 3 PRINCESS IGGGI GGGGG GGGGG GGGGG GGGGI HOUSE 4 4 CASTLE 0 0 PRINCESS 4 0
Output
17
Hall of the Mountain King Test
Input
5 5 4 TREASURE IMMMI MMMMM GGIMM GGGGG IGGGG HOUSE 0 4 CASTLE 4 0 STABLE 2 2 TREASURE 0 0
Output
25
Hall of the Mountain King Validator
Input
5 5 4 TREASURE MMMMI MMMMM IGIMM GGGGG GGGGI HOUSE 4 4 CASTLE 4 0 STABLE 2 2 TREASURE 0 2
Output
21
The River Test
Input
5 5 4 DRAGON IGGGI GGGGG WWWWW GGGGG IIGGG HOUSE 0 4 CASTLE 0 0 BLACKSMITH 1 4 DRAGON 4 0
Output
17
The River Validator
Input
5 5 4 DRAGON IIGGG GGGGG WWWWW GGGGG GGGII HOUSE 4 4 CASTLE 1 0 BLACKSMITH 3 4 DRAGON 0 0
Output
11
Rise of the Chaos Wizards Test
Input
5 5 4 TREASURE GGGGI IGGGG RRRRR IGGGG GGGGI HOUSE 4 4 CASTLE 4 0 WIZARD 0 3 TREASURE 0 1
Output
18
Rise of the Chaos Wizards Validator
Input
5 5 4 TREASURE GGGGI GIGGG RRRRR IGGGG GGGGI HOUSE 4 4 CASTLE 4 0 WIZARD 0 3 TREASURE 1 1
Output
16
Iron Man Test
Input
5 5 5 PRINCESS RRIRR RRIRR RRGRR GGGIG IGGGI HOUSE 0 4 CASTLE 4 4 BLACKSMITH 3 3 DRAGON 2 1 PRINCESS 2 0
Output
16
Iron Man Validator
Input
5 5 5 PRINCESS RRIRR RRIRR RRGRR GIGIG GGGGI HOUSE 1 3 CASTLE 4 4 BLACKSMITH 3 3 DRAGON 2 1 PRINCESS 2 0
Output
14
To Hell and Back Test
Input
5 6 6 TREASURE ISSSS RRRSS RRIRR RGGGR GGGGI IGIIG HOUSE 0 5 CASTLE 4 4 STABLE 2 5 BLACKSMITH 3 5 DRAGON 2 2 TREASURE 0 0
Output
31
To Hell and Back Validator
Input
5 6 6 TREASURE ISSSS RSSSS RRIRR RGGGR GGGGI IGIIG HOUSE 0 5 CASTLE 4 4 STABLE 2 5 BLACKSMITH 3 5 DRAGON 2 2 TREASURE 0 0
Output
19
Thunderhorse Test
Input
14 14 5 DRAGON WWRRRMMMMMMMMM RWWWRIMMMMMMMW RRRWWGGMMMIGWW MMRRWGGGGGGWWW MMSSWGGGIGWWWW MMSSWWWGGGGWWW MSSSSSWWGGGGWW MSSSSSSWWIGGWW MMISSSSSSWWWWW MMMSSSSSSSGWWW MMMGGGGGSGGGWW MMGGWWWGGGWWWW MWWWWWWWWWWWWW WWWWWWWWWWWWWW HOUSE 10 2 CASTLE 5 1 STABLE 8 4 BLACKSMITH 9 7 DRAGON 2 8
Output
27
Thunderhorse Validator
Input
14 14 5 DRAGON WWRRRMMMMMMMMM RWWWRIMMMMMMMW RRRWWGGMMMIGWW MMRRWGGGGGGWWW MMSSWGGGIGWWWW MMSSWWWGGGGWWW MSSSSSWWGGGGWW MSSSSSSWWIGGWW MMSSSSSSSWWWWW MMMSSSISSSGWWW MMMGGGGGSGGGWW MMGGWWWGGGWWWW MWWWWWWWWWWWWW WWWWWWWWWWWWWW HOUSE 10 2 CASTLE 5 1 STABLE 8 4 BLACKSMITH 9 7 DRAGON 6 9
Output
23
Carry On Test
Input
10 10 7 TREASURE IIMMRRSISS RRRRMRSSSS RMMMRRSSSS MRRRRMSSSS GMMMMSSGGS IGWWWWWWGS GWWWWWWWWG GWWIIWWWWG GGWGWWWWGG GIGGGGGGGG HOUSE 1 9 CASTLE 3 7 BLACKSMITH 4 7 STABLE 0 5 WIZARD 7 0 DRAGON 1 0 TREASURE 0 0
Output
71
Carry On Validator
Input
10 10 7 TREASURE IIMMRRSISS RRRRMRSSSS RMMMRRSSSS MRRRRMSSSS GMMMMSSGGS GGWWWWWWGS IWWWWWWWWG GWWIIWWWWG GGWGWWWWGG GIGGGGGGGG HOUSE 1 9 CASTLE 3 7 BLACKSMITH 4 7 STABLE 0 6 WIZARD 7 0 DRAGON 1 0 TREASURE 0 0
Output
72
Solution language
Solution
Stub generator input
ABOUT USCAREERSPRIVACYFAQBLOG
ABOUT USCAREERSPRIVACYFAQBLOG

The #1 tech hiring platform

SCREENINGINTERVIEWING
FacebookYouTubeTwitterLinkedIn