back to the menu

Flag Counter TopCoder SRM 575 - 1000: TheTilesDivOne

SRM 575 1 1000 TheTilesDivOne


Problem Statement

现在有一个 n*m 的网格图,网格图的每个格子都有颜色,要么是黑色要么是白色,
对于第i行j列的格子,假如i+j是偶数,那么这个格子是黑色的,否则是白色的。
现在有些格子上放了障碍物,剩下的格子是空的。
你有足够多的L型瓷砖,每个恰好能覆盖3个格子,他们看起来是这样的:

OO
O

现在你需要把这些瓷砖放到网格图上,满足:
1. 每块瓷砖都可以旋转任意多次90度
2. 每块瓷砖必须恰好覆盖3个格子
3. 瓷砖之间不能有任何位置重叠
4. 瓷砖不能覆盖到有障碍的格子
5. 瓷砖的转折处必须放在一个黑色格子上

现在问你最多能放多少瓷砖?

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.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • board {"X.X",
       "...",
       "X.X"}
    output
    Returns 1
    note
    Since only one black cell is available, just one tile can be placed on the board.
  2. input
    • board {"...",
       "...",
       "..."}
    output
    Returns 2
  3. input
    • board { "......X.X.XXX.X.XX." }
    output
    Returns 0
  4. input
    • board {"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..."}
    output
    Returns 13

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.