Connection Status:
Competition Arena > BrokenChessboard

BrokenChessboard

SRM 729 · 2018-02-08 · by erinn

SRM 729 · 2018-02-08 · by erinn · Brute Force
Class Name: BrokenChessboard
Return Type: int
Method Name: minimumFixes
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A chessboard consists of alternating black and white squares: every square differs in color from the squares that are adjacent to it vertically and horizontally.

You are given a rectangular board of black and white squares in a String[] board. However, the coloring of the squares might not match the chessboard coloring scheme. Each string in board represents a row of squares of the board, and each character (all either 'B' or 'W') represents a square in that row. Return the minimum number of squares that would need their color swapped for the given board to become a valid chessboard.

Constraints

  • board will contain between 1 and 50 elements, inclusive.
  • Each element of board will contain between 1 and 50 characters, inclusive.
  • Each element of board will be the same length.
  • Each character of each element of board will be either 'B' or 'W'.
Examples
0)
{"BWB",
 "BBW",
 "BWW"}
Returns: 2

There are two ways to fix this board: BWB WBW WBW BWB BWB WBW The result on the left would require changing 2 squares (center-left and bottom-right). The result on the right would mean changing 7 squares, so the former is a better choice.

1)
{"WW",
 "WW"}
Returns: 2

Either of the two valid boards we could make would take exactly 2 changes.

2)
{"BWB",
 "WBW",
 "BWB"}
Returns: 0

This board is already valid, so no fixes are needed.

3)
{"B",
 "W",
 "B",
 "B"}
Returns: 1

The board is not square, but anyways it only needs 1 square changed.

4)
{"BWBBB",
 "WWBBW",
 "BBBBW",
 "WBWBB"}
Returns: 7

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

Coding Area

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

Submitting as anonymous