Pickaxe | Topcoder Archive

Problem Statement

You are given the String[] maze that describes a rectangular maze. The maze is divided into R rows by C columns of cells. Both rows and columns are numbered starting from 0. The character '.' represents an empty cell, the character '#' represents a wall. Implicitly, the maze is surrounded by additional walls that are not given in the input.

You start in the cell (0, 0) and your goal is to reach the cell (R-1, C-1). In each step, you can move from your current cell to one of the horizontally or vertically adjacent cells. Of course, you cannot walk into a wall.

Reaching your goal is currently impossible. Luckily for you, you are carrying a pickaxe. The pickaxe can be used exactly once to break a wall that is horizontally or vertically adjacent to your current cell.

Find all walls such that if you use the pickaxe to break the wall, it will be possible to reach the cell (R-1, C-1). Return the number of such walls.

Definition

Class:: Pickaxe
Method:: countWalls
Parameters:: String[]
Returns:: int
Method signature:: int countWalls(String[] maze)
(be sure your method is public)

Constraints

R will be between 2 and 100, inclusive.
C will be between 2 and 100, inclusive.
maze will contain R elements, each containing C characters.
Each character in maze will be either '.' or '#'.
maze[0][0] will be '.'.
maze[R-1][C-1] will be '.'.
It will not be possible to walk from (0, 0) to (R-1, C-1).

Examples

```
{"..#",
 ".#.",
 "#.."}
```
```
Returns: 3
```
Here we can use the pickaxe to dig through any of the three walls.
```
{"..##..",
 "..##..",
 "...#..",
 "..##.."}
```
```
Returns: 1
```
This time there is just one candidate: the wall in row 2, column 3.

{"..##..",
 "..##..",
 "..##..",
 "..##.."}

Returns: 0

{".....#.",
 ".###.#.",
 ".#.#...",
 ".###.##",
 ".#.#.#.",
 ".#.###.",
 "##....."}

Returns: 6

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.