Filter

SRM 89 · 2002-05-16 · by dgoodman

Class Name: Filter

Return Type: int

Method Name: removable

Arg Types: (vector<string>)

Problem Statement

A 2-dimensional digital picture has been received from a satellite as a String[]. The characters in each String are only '0' or '1' (zero or one). Some of the '1's are noise that should be filtered out. The filtering rule is that a '1' should be removed if it is not part of a cross pattern consisting of 5 '1's in the following configuration:

     1
    111
     1

Write a class Filter that contains the method removable that takes a String[], picture, and returns the number of '1's that should be filtered out of picture.

Notes

Cross patterns may overlap. (See example 2)

Constraints

picture contains between 1 and 50 elements, inclusive.
each String in picture contains between 1 and 50 characters, inclusive.
each String in picture has the same length.
each String in picture contains only the characters '0' and '1' (zero and one).

Examples

{"00110",
 "00110",
 "00110"}
Returns: 6

There are no cross patterns. All the '1's can be removed.

{"00110",
 "00111",
 "00110"}
Returns: 2

There is one cross pattern. 2 of the '1's can be removed.

{"00111",
 "01111",
 "00110"}
Returns: 1

There are two (overlapping) cross patterns. Only the 1 in the upper right corner is not in some cross.

{"01000","11100","01110","00110"}
Returns: 1

{"1111","1001","1111"}
Returns: 10

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

Coding Area

Language: C++17 · define a public class Filter with a public method int removable(vector<string> picture) · 27 test cases · 2 s / 256 MB per case