Connection Status:
Competition Arena > SymmetryDetection

SymmetryDetection

SRM 713 · 2017-02-20 · by cgy4ever

SRM 713 · 2017-02-20 · by cgy4ever · Brute Force
Class Name: SymmetryDetection
Return Type: String
Method Name: detect
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Fox Ciel has a rectangular board divided into n rows by m columns of unit square cells. Rows are numbered 0 through n-1 from top to bottom and columns are numbered 0 through m-1 from left to right. Each cell is either white or black. You are given a String[] board containing the description of the board. The character board[i][j] represents the cell in row i, column j. The character '#' represents a black cell and '.' represents a white cell.

The board is called horizontally symmetric if it remains the same when flipped around a horizontal line that goes through the center of the board. If n is odd, this line goes through the middle of row (n-1)/2. If n is even, the line goes between rows (n/2)-1 and (n/2).

Similarly, the board is called vertically symmetric if it remains the same when flipped around a vertical line that goes through the center of the board.

Please help Ciel determine the types of symmetry of her board. Return one of the following four Strings:

  • "Both" if Ciel's board is both horizontally and vertically symmetric.
  • "Horizontally symmetric" if Ciel's board is horizontally symmetric but not vertically symmetric.
  • "Vertically symmetric" if Ciel's board is vertically symmetric but not horizontally symmetric.
  • "Neither" otherwise.
Note that the quotes are for clarity only. Also note that the return value is case-sensitive.

Notes

  • The values n and m are not given explicitly. Instead, you can determine n as the number of elements in board and m as the length of any element in board.

Constraints

  • n, m will be between 1 and 50, inclusive.
  • board will contain exactly n elements.
  • Each element in board will have exactly m characters.
  • Each character in board will be '#' or '.'.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"#####",
 ".###.",
 "..#.."}
Returns: "Vertically symmetric"

If we flip this board according to the vertical line that goes through the middle of column 2, we will get exactly the same board. On the other hand, if we flip it according to the horizontal line that goes through the middle of row 1, we will get the following shape: ..#.. .###. ##### This is not the same board, which means that this board isn't horizontally symmetric.

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

This time it is both horizontally and vertically symmetric.

2)
{"#..",
 "#..",
 "#.."}
Returns: "Horizontally symmetric"
3)
{"#.",
 ".#"}
Returns: "Neither"
4)
{"#######",
 "#..#..#",
 "#######",
 "...#...",
 "#######"}
Returns: "Vertically symmetric"

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

Coding Area

Language: C++17 · define a public class SymmetryDetection with a public method string detect(vector<string> board) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous