MovingCandies | Topcoder Archive

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.

Definition

Class:: MovingCandies
Method:: minMoved
Parameters:: String[]
Returns:: int
Method signature:: int minMoved(String[] t)
(be sure your method is public)

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.
```
{
"..",
".."
}
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.