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.