Cookie Crew
InterviewTime limit1sMemory limit512 MB
On an N x N grid with three of each topping type, find which topping type gives the shortest path from the house to the goal, visiting all three cells of that type.
- Level
Medium5 of 10
- Topics
- BFS, Graph, Brute force, Shortest path
- Solved
- No attempts yet
Problem
Kim Cookie, baked to a nice finish from flour dough, is a citizen of Cookie Country, which stands on a wide, flat field. Kim Cookie always wondered what could be done to protect Cookie Country, which has been struggling under Cake Country's invasion. One day, while walking and thinking, Kim Cookie found a flyer recruiting for Cookie Crew, Cookie Country's knight order. To apply to Cookie Crew, one must wear three toppings on the body that match the desired division. The toppings that suit each Cookie Crew division are as follows.
- Assassin - Jelly (J)
- Healer - Chocolate (C)
- Mage - Berry (B)
- Tanker - Walnut (W)
Kim Cookie decided to join Cookie Crew, but since the competition is fierce, the application must be submitted as quickly as possible. Kim Cookie hurried home and took out the Topping Topping Map, a two-dimensional N × N grid, to check the positions of each topping. The map marks the positions of the Walnut, Chocolate, Berry, and Jelly toppings, three of each, along with the position of the house (H) and Cookie Crew Pping Pping (#), the place where one applies to Cookie Crew. Kim Cookie looks at the map, checks where the toppings lie, then must wear three toppings of the same kind and go to Cookie Crew Pping Pping.
For Kim Cookie, who wants to apply to Cookie Crew as quickly as possible, look at the map and tell which division Kim Cookie should apply to.
Kim Cookie can move up, down, left, and right on the map, one cell at a time, and may visit the same place multiple times.
On arriving at Cookie Crew Pping Pping, it does not matter if toppings other than those of the division being applied to are worn as well, and even when the application cannot yet be made, Kim Cookie may pass through Cookie Crew Pping Pping to move elsewhere.
Input
The first line of input gives N, the size of the Topping Topping Map. (4 ≤ N ≤ 100)
From the second line, N lines give the Topping Topping Map across N cells each. In the map, X is empty ground, H is the house, W, C, B, and J are the Walnut, Chocolate, Berry, and Jelly toppings respectively, and # is Cookie Crew Pping Pping, the place where one applies to Cookie Crew.
The map is guaranteed to contain three of each topping and one house and one Cookie Crew Pping Pping.
Output
Print the division Kim Cookie should apply to.
If the application should be to the Assassin division, print "Assassin"; for Healer, "Healer"; for Mage, "Mage"; for Tanker, "Tanker".
If there are several divisions Kim Cookie can apply to, the priority order is Assassin, Healer, Mage, Tanker.