Connection Status:
Competition Arena > TheTilesDivOne

TheTilesDivOne

SRM 575 · 2012-12-13 · by Vasyl[alphacom]

SRM 575 · 2012-12-13 · by Vasyl[alphacom] · Brute Force
Class Name: TheTilesDivOne
Return Type: int
Method Name: find
Arg Types: (vector<string>)
Problem Statement

Problem Statement

John and Brus have a rectangular chessboard with black and white tiles. Rows and columns of the chessboard are numbered starting from 0. The cell at row i, column j is black if i+j is even and it is white if i+j is odd.

Some of the cells of the chessboard are occupied by chess pieces. You are given a String[] board. For each i and j, the j-th character of the i-th element (0-based indices) of board is 'X' if the cell in row i, column j of the chessboard contains a chess piece. Otherwise, the j-th character of the i-th element of board is '.'.

John and Brus also have an infinite supply of L-shaped tiles. Each tile consists of three squares which are of the same size as the cells of the chessboard. I.e., each tile looks as follows: 
OO
O
John and Brus want to place some of the tiles onto their chessboard, according to the following rules:
  • Each tile may be rotated by any multiple of 90 degrees.
  • Each tile must cover exactly three cells of the chessboard.
  • Tiles are not allowed to overlap.
  • Tiles are not allowed to cover the cells that are already occupied by the chess pieces.
  • The corner cell of each tile must cover a black cell of the chessboard.


Return the maximum number of tiles John and Brus can place on the board according to the above rules.

Constraints

  • board will contain between 1 and 47 elements, inclusive.
  • Each element of board will contain between 1 and 47 characters, inclusive.
  • All elements of board will contain the same number of characters.
  • Each element of board will consist of only characters 'X' and '.'.
Examples
0)
{"X.X",
 "...",
 "X.X"}
Returns: 1

Since only one black cell is available, just one tile can be placed on the board.

1)
{"...",
 "...",
 "..."}
Returns: 2
2)
{"......X.X.XXX.X.XX."}
Returns: 0
3)
{"X.....XXX.XX..XXXXXXXXX...X.XX.XX....X",
 ".XXXX..X..XXXXXXXX....XX.X.X.X.....XXX",
 "....XX....X.XX..X.X...XX.X..XXXXXXX..X",
 "XX.XXXXX.X.X..X..XX.XXX..XX...XXX.X..."}
Returns: 13
4)
{"XX..XXXXXXXXX.XXX.XXX...", "...X.XXXXXX.X..X...XX.XX", "X.X.X.X..X.X.XX.X.X...X.", "..X.XXXX..XXX...XX....X."}
Returns: 8

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

Coding Area

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

Submitting as anonymous