EllysViewPoints

TCO19 SRM 759 · 2019-05-28 · by espr1t

TCO19 SRM 759 · 2019-05-28 · by espr1t · Simple Search, Iteration

Show categories

Class Name: EllysViewPoints

Return Type: int

Method Name: getCount

Arg Types: (int, int, vector<string>)

Problem Statement

Elly has a rectangular matrix with N rows and M columns. Each of the cells in the matrix can be either blocked (denoted '#') or free (denoted '.').

An empty cell is called a view point if we can see outside the matrix when looking directly in each of the four cardinal directions: north, south, east, and west. In other words, a cell C is a view point if and only if all cells in those four directions from cell C are free.

Below is an example matrix that contains six view points. One of these is marked by an asterisk ('*').

..#......
.....*...
.###..#..
.#.##..#.
...#..#..
.........

The girl has given you the ints N and M, as well as the String[] matrix. Return the number of view points in the given matrix.

Constraints

N will be between 1 and 50, inclusive.
M will be between 1 and 50, inclusive.
matrix will contain exactly N elements.
Each element of matrix will contain exactly M characters.
Each character in matrix will be either '#' or '.'.

Examples

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

The example from the problem statement.

1
1
{"."}
Returns: 1

It's pretty obvious which cell is the view point.

7
4
{"####",
 "####",
 "####",
 "####",
 "####",
 "####",
 "####"}
Returns: 0

With everything blocked, there are obviously no view points.

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

Good luck!

20
33
{"...#............#.........#......", ".................................", "................#.....#.#......#.", ".................................", "........#..............##..#.....", "...#.....#.............#..##...#.", "....................##..#.#......", ".......#..............#...##.....", ".........#......#...#..#...#.....", "......................#....#.....", "..........................#......", ".................#..#.#...#......", ".................................", ".......................##.#......", "#......#.#...........#....#......", "#......#..............#...##.....", ".................................", "........#........................", ".................................", ".......................#........."}
Returns: 90

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

Coding Area

Language: C++17 · define a public class EllysViewPoints with a public method int getCount(int N, int M, vector<string> matrix) · 58 test cases · 2 s / 256 MB per case