Statistics

Problem Statement for "TheTilesDivTwo"

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.

Definition

Class:
TheTilesDivTwo
Method:
find
Parameters:
String[]
Returns:
int
Method signature:
int find(String[] board)
(be sure your method is public)

Constraints

  • board will contain between 1 and 4 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

  1. {"X.X", "...", "X.X"}

    Returns: 1

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

  2. {"...", "...", "..."}

    Returns: 2

  3. {"......X.X.XXX.X.XX."}

    Returns: 0

  4. {"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

  5. {"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

  6. {"...", "XX.", "..X"}

    Returns: 1

  7. {".", "X"}

    Returns: 0

  8. {"..X.XX.X.XX..XXXXXXXX.XX.XX...X..X.XX.XX.X.X.X.", "....X.XX...XXXXX.X.XX.X.X.XXXXXX..XX......XX.X.", ".......X.XX.X...XX.X.XX..XX..X...X.......XXXXX.", ".....X.XXXXX.X.XXXXXXXX...XX....XX....XX.XX.XXX"}

    Returns: 14

  9. {".X.XX..XXX.X.", "X.XXX.X..XXXX"}

    Returns: 0

  10. {"..XX.XXXXX..X...XX.X.XX..XX.X.X....", ".XX..X..XX.XX.XX.XXX.XX.X..XXXX.X.X", "XX.XX...XXXX...X..X....XXXXX..XXX.X", "..XXX..X........X.........XXXX.X.XX"}

    Returns: 8

  11. {".X...X.X.X.X...X...X.......X.X.X.X.....X...", "X...X.........X.X.X...............X.X...X..", "...X.......X...X.....X...X...X.X.....X...X.", "X.X.X.X...X...X.....X.X...............X...X"}

    Returns: 18

  12. {".X.X.X.......X.X.X...X.......X.X..........", "X.......X.X.X...X...X...X.......X.X.X.....", ".X.X.X.X.X.X.X.X.X.....X.....X.....X.X...X", "X...X.X...X.X.X.X.X.X.X...X.X.X...X.X.X.X."}

    Returns: 10

  13. {"...X.....X...X.X.X.....X...X...X.X...X.X.X.X..", "X...X.X.X.X.X.X.....X.X...X.......X.X.X...X...", "...X...X...................X.X.X.X.X...X......", "......X.X.X...X.....X.X.............X.X.X.X..."}

    Returns: 15

  14. {".............X.............X.X.....X.....X...", "X.X.....X.X.....X.......X.X...X.X.X.X.X.X.X..", ".X...X.X.................X.X...........X.X...", "X.X.X.X.....X.X.....X.....X.....X.X.X.....X.."}

    Returns: 18

  15. {".X.....X.X...X.X.X.....X.....X.......X...X.X", "X.X.........X.X...X.X...X.......X.X.X.X...X.", ".X...X...X.............X.....X.X.....X...X..", "........X...X.X.X.X.X.X.X...X.X.X...X.X.X.X."}

    Returns: 14

  16. {".X...X.X.X...X.X.X.X.....X...X.X.X.......", "....X.....X.....X.....X.....X.....X.X.X..", ".X.X.......X...X...X.X.X.X.X...X.....X.X.", "..X.....X.X...X.X.X...X.X...X.X...X.X.X.X"}

    Returns: 13

  17. {".X...X.X.X.X.X...X.............X.X.X...X.X.X.X", "......X.X.X.X...X.X...X...X.....X.X...X.X.X.X.", ".X.X.X.......X...X.X...X.X...........X.....X..", "X.X.X.........X.X...X...X.X...X...X...X.X...X."}

    Returns: 15

  18. {".X.X.X.X.X.X.X.X...X.X.X...X...X.X...X.....X", "X...X.....X...............X.X.......X...X...", "...X...X...X.X...X...X.X...X.......X.X.X.X..", "X.X...X.X...X.X.....X...X.X.X.X.X.X.X...X..."}

    Returns: 13

  19. {"...X.X.X.....X...X...X.X...X.X.X.X.....X..", "....X.X...X...X.X.X.......X.X.X.....X.X.X.", "...X...X.....X...X.....X...X.....X.....X..", "..X.....X.X.X.X.......X.X.....X.......X.X."}

    Returns: 16

  20. {".X.....X.X...X.......X.X.........X.X.....X.X.X", "..X...X.X.X...X.X.....X...X.....X.X.X...X.....", ".X.......X.X...X.X...............X.....X.X.X..", "..X.X.X.X...X.....X...X.X.X.X.X...X.X...X.X..."}

    Returns: 13

  21. {"...............................................", "...............................................", "...............................................", "..............................................."}

    Returns: 46

  22. {"..............................................", "..............................................", "..............................................", ".............................................."}

    Returns: 46

  23. {"XX...X.X.XXX..XX..XX.....X.X.X.XXX.X...X...XX.", "X.X.X.X.X.......X.X.X...X...X.XXXX..X.X...X.X.", "...X.X...X.X...XX.XX...X.X..X..X...XXXXX.X.X..", "X....X..X.XX.XX.X.X.X.....X.XX..X.X.XX...XX.X."}

    Returns: 10

  24. {".X.X.X..XX.......X.X...........X.X...XX...XX.", ".XX..X............XXX.......X.XXX.X.X.XXX.XXX", "X....X.....X....XX.X...X.X..X..X...XX...X..X.", "....XXX.....X...X.X...X.X.X..X.XX...X.X.X...."}

    Returns: 18

  25. {"X..X..XX.X.X.X.X.X.XX.X..X.XXX...XX..X...X.X...", "....X.....X.XXX.X.X.X.X.X...X...X...X.X.......X", "XX.X.X.XXX..XX..X.X..X.X..X..X...XX..X.X.XX...."}

    Returns: 8

  26. {"..X.X..X.X.X.X...XX....X...X.X.X...X.......X", "X.X.X..X..X.....XX..X.X....XX.X...X.XXXX....", ".....X.XXXXXX..X......X...XXX..X.........X..", "..XXX...........X.X...XXXXXXX.....XXXX....XX"}

    Returns: 15

  27. {".XXX.X..X.........XX.X.....X........X...XX..", "..XX....X..XX...XX.XXXXX.XX...X.X...XX..XX.X", "..XX.......X.XXX.X..XX.XXX...X..XX.X...X.X.X", "..XX.XX.X.X..X.XX...XX....X.X.....X.X..XXX.."}

    Returns: 13

  28. {".X...X.XXX...X.X.X.X.X.X....XX.X.X.X...XXX.X..", "..X..XX.X.X......XXX..X.X...X.....XXX..XXX....", "XX...XX.XXXX...XX..X.X.X...X.X.XXX.....X....XX"}

    Returns: 7

  29. {".X.XX..X...X.XX..X...XX.X....XXX.XX....X.XXXX", "X.X.X.X..X.XX..X....XX....X.X.X.X...X.X......", "XXXX....X..X.X.X.X...X.X.X.X.XXX.....XXX...X."}

    Returns: 8

  30. {".X...X.X.XXX..XX..XX.......X.X.X.X.....X...X...", ".....X........................X.X........X.....", "...X...X.....X...X...X.X.....X...X.XXX.X.X...X.", "..X.....X.X...............X...XX..X...X..X....X"}

    Returns: 20

  31. {".X...X.......X.X...........X.X...X.....X...X...", "............X.X.......X.X...X...X.X.X.......X..", "...X.....X.X...X.......X....X......X.....XXX...", "......X.....X...X..X.X....X.X.X.........X...X.."}

    Returns: 25

  32. {".X.X.X.X..X..X.XX....X.......X.X.......X.....X.", "......X.X...........................X.X...X....", ".X..X.X..X.X..........X..X...XX........X.X...X.", "........X........................X....X.....X.."}

    Returns: 26

  33. {".X...X.X.....X.X.....X.......X.X..X..X.X.X.X.X.", "....X...X.X.................XXX...........X.X..", ".X.X.X.X.....X.X.....X.....X.....X.X.X.....X...", "..............X...X......X............X..X..X.."}

    Returns: 20

  34. {"...X.X...X...X..XX.X.......X.X.X..X..X...X...X.", "..X.............XX....X.X..X..X.........X......", ".X.X..XXX..XXX.X.X.X.X..............XX...X.XXX.", "......X.......X..X..X.X...........X.....X.....X"}

    Returns: 20

  35. {"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}

    Returns: 0

  36. {"X.X......X.X.X.......X...X.X...X.X........X..X.", "....X...X.......X.....X.X...X.....X...........X", ".X.X..XX.X.X.X.X.X.X.X.X.....X.X...X.....X...X.", "....X..........XX...X.X..........XX...X...X...."}

    Returns: 19

  37. {"...X...X...X.X...X...X.....X.......X.X.X.X.....", "..........X.X.X...X.......X.X.....X...X.......X", ".X.X.....X...X...X.X...X.X.X.X..X..X...X...X.X.", "X.............X.......X....X..X.....X......X..."}

    Returns: 20

  38. {".X.....X...X.....X.....X.......X.X.........X...", "....................X...............X.......X.X", ".........X.X.....X...X.X........XX...X.X.X.X...", "........X.......X.............X.X...X......X..."}

    Returns: 27

  39. {"..X..X.....X.X.X...X.X.X.X.......X.X.X...XXX.X.", ".....X..........X...................X..........", "...X.X..X....X.X.X...X.....X.X.X............XX.", "......X.........X.X.................X.....X...."}

    Returns: 22

  40. {".....X.X.X...........X...............X.........", "..X...X....X....X.X...X.....................XXX", ".....X.....X.X.....X.X.X.X.......X..X...X....X.", "..X.................X...................X......"}

    Returns: 30

  41. {"XX..XXXXXXX.X.XX", "..XX.......X.X.X", "XXX.X.X....XX.X.", "....X....X.X.X.."}

    Returns: 5

  42. {"X...X...X.XXXX..X.X...X.X...X..X...XX.", "...X...X...X.X.....X...X.XXX.X.X...X..", ".X..X.XX.XX.X.X.X.....X.XX..XXX.XX...X", "..X....X.X.X...X.......X.X...........X"}

    Returns: 22

  43. {"...XX.X.XX.", ".X...X...X.", "X.....XXXXX", "........XX."}

    Returns: 5

  44. {"...XXXXXX.X...XX....XX....XX.XX.XXX...X.XX..X.X", ".X.X.XXX.X...X.X.X...X.XXX.X......XX.X.X...X...", ".X......X..X..XX..X.X...XX..X.X..XX.X.X.X.X.X..", "...X.X...X..X....X.X.X...X.XX..X.X.........X.X."}

    Returns: 27

  45. {"X.X.X.X.X.X.X.XXX.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.X.X.X.X", "X.X.X.X.X.X.X.X.XXX.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.X.X.X.X"}

    Returns: 0

  46. {".X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.", "......X..............................", ".X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.", "....X.X.....X.......X.X.X.......X...."}

    Returns: 0

  47. {"XX..XXXXXXX.X.XXX.XXX.....X..XX.XXX.X", "XXX.X.XXXXXXXXXXXXXXXXXXXXXXXXX.XXX.X", "X.XXXX..X.X...XXX...X.XX...XX...XXX.X", "XXX.XXXXXXXXXXXXXXXXXXX.XXXXX.X.X.XXX"}

    Returns: 0

  48. {"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

  49. {"X.....XXX.XX..XXXXXXXXX...X.XX.XX....X", ".XXXX..X..XXXXX.XX....XX.X.X.X.....XXX", "....XX....X.XX..X.X...XX.X..XXXXXXX..X", "XX.XXXXX.X.X..X..XX.XXX..XX.X.XXX.X..." }

    Returns: 13

  50. {"...............................................", "...............................................", "...............................................", "..............................................." }

    Returns: 46

  51. {"....", "....", "...." }

    Returns: 2

  52. {"X.X", "...", "X.X" }

    Returns: 1

  53. {"X...", "....", ".X.." }

    Returns: 2

  54. {"X.....XXX.XX..X...XXXXX...X.XX.XX....X", ".X..X..X..XXXXX.......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: 15

  55. {".....XXX.....XX...XXXX..X....XX....XXXXXX...X.X", "..X..X.X.....X....XX.X..X....XX.X.......X...XXX", "X..X.X.X.....XX...XX.X..X....XX....XX...X..XX.X", "....XXX......XX...X..X..X....XXXX..X....X...X.X" }

    Returns: 22

  56. {"XX..XXX.....X...X.XX.XX....X", "XX....XX....XX.X.X.X.....XXX", "X.XX..X.X......X..XXXXXXX..X", ".X..X..XX......XX.......X..." }

    Returns: 12

  57. {"...............", "...............", "...............", "..............." }

    Returns: 14

  58. {"..X...X......XX...X....X.X.X.X.X.XXX......XX...", "....XX..X...X.......XX........XXX..X..X..X...XX", "X.X....X.....XX.X.X.X..X..X..X..X..XX......XXXX", "....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.....XXX" }

    Returns: 18

  59. {".X", "XX" }

    Returns: 0

  60. {"X.", ".." }

    Returns: 1

  61. {"X..", "X.X" }

    Returns: 0

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: