Connection Status:
Competition Arena > Squares

Squares

SRM 332 · 2006-12-28 · by andrewzta

SRM 332 · 2006-12-28 · by andrewzta · Search, Simple Math
Class Name: Squares
Return Type: int
Method Name: countSquares
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a rectangular field divided into square cells. Each cell contains a letter. A square with vertices in the centers of four cells is called valid if those four cells are distinct and all contain the same letter. For example, the following field contains two valid squares: 

ABA
BAB
ABA

One has vertices in the centers of the following squares: 

A.A
...
A.A

Another has vertices in the centers of the following cells: 

.B.
B.B
.B.

You are given a String[] field. The j-th character of the i-th element of field is the letter contained in the cell at row i, column j. Return the number of distinct valid squares in the field. Two squares are distinct if one has a vertex in a cell where the other does not.

Constraints

  • field will contain between 1 and 50 elements, inclusive.
  • Each element of field will contain between 1 and 50 characters, inclusive.
  • All elements of field will contain the same number of characters.
  • Each element of field will contain only uppercase letters ('A'-'Z').
Examples
0)
{"ABA", "BAB", "ABA"}
Returns: 2

Example from the problem statement.

1)
{"AA", "AA"}
Returns: 1
2)
{"ABC", "DEF", "GHI"}
Returns: 0

There are no valid squares here.

3)
{"AABCA", "AAAAA", "BAAAB", "AAAEA", "ADBFA"}
Returns: 11
4)
{"A"}
Returns: 0

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

Coding Area

Language: C++17 · define a public class Squares with a public method int countSquares(vector<string> field) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous