MovingCandies

SRM 706 · 2016-12-07 · by Errichto

SRM 706 · 2016-12-07 · by Errichto · Dynamic Programming, Search

Show categories

Class Name: MovingCandies

Return Type: int

Method Name: minMoved

Arg Types: (vector<string>)

Problem Statement

Limak is a little bear. He is currently planning a walk on a rectangular grid. Each cell of the grid is either empty or it contains a single candy. Empty cells are denoted '.', cells with a candy are denoted '#'.

Limak wants to go from the top-left corner to the bottom-right corner of the grid. Since he loves sweets, there should be a candy in each cell he visits, including the starting and the final cell. He can only move in the four cardinal directions. In other words, he can move from cell A directly to cell B if and only if A and B share a side.

You are given the String[] t: the current state of the grid. Limak's journey may be impossible on the current grid. Your task is to make it possible by moving as few candies as you can. Moving a candy means picking it up and placing it into any empty cell.

Return the smallest number of candies that have to be moved in order to make Limak's journey possible. If there is no solution, return -1 instead.

Constraints

t will have between 2 and 20 elements, inclusive.
Each element of t will have between 2 and 20 characters, inclusive.
Each element of t will have the same number of characters.
Each character in each element of t will be either '.' or '#'.

Examples

{
"#...###",
"#...#.#",
"##..#.#",
".#....#"
}
Returns: 3

You must move at least 3 candies. One way of doing so is shown in the grid below. Candies were moved from cells denoted 'o' to cells denoted 'X'. #...### #XXX#.# oo..o.# .#....#

{
"#...###",
"#...#.#",
"##..###",
".#....#"
}
Returns: 2

2 moves are enough in this example: #...### #...#.# ##XX#o# .o....#

{
".#..",
"##..",
"..#.",
"..#.",
"..##",
"..##"
}
Returns: 2

Note that the starting and the final cell should both contain candies.

{
".....",
".###.",
"####.",
"....."
}
Returns: -1

No matter how you move candies, Limak won't be able to get from the top-left to the bottom-right corner.

{
".#...#.###.#",
"#.#.##......",
".#.#......#.",
"..#.......#.",
"##.........."
}
Returns: 9

{
"###.#########..#####",
".#######.###########"
}
Returns: 0

You don't have to move any candies. Limak can already go from the top-left to the bottom-right corner.

Submissions are judged against all 100 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MovingCandies with a public method int minMoved(vector<string> t) · 100 test cases · 2 s / 256 MB per case