Connection Status:
Competition Arena > Pickaxe

Pickaxe

TCO19 SRM 761 · 2019-06-21 · by misof

TCO19 SRM 761 · 2019-06-21 · by misof · Recursion, Search
Class Name: Pickaxe
Return Type: int
Method Name: countWalls
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"..#",
 ".#.",
 "#.."}
Returns: 3

Here we can use the pickaxe to dig through any of the three walls.

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

This time there is just one candidate: the wall in row 2, column 3.

2)
{"..##..",
 "..##..",
 "..##..",
 "..##.."}
Returns: 0
3)
{".....#.",
 ".###.#.",
 ".#.#...",
 ".###.##",
 ".#.#.#.",
 ".#.###.",
 "##....."}
Returns: 6
4)
{".#","#."}
Returns: 2

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

Coding Area

Language: C++17 · define a public class Pickaxe with a public method int countWalls(vector<string> maze) · 28 test cases · 2 s / 256 MB per case

Submitting as anonymous