Statistics

Problem Statement for "PathGameDiv2"

Problem Statement

Cat Snuke is playing the Path Game.


The Path Game is played on a rectangular grid of square cells. The grid has 2 rows and some positive number of columns. Each cell is either black or white.


A left-to-right path in the grid is a sequence of white cells such that the first cell in the sequence is in the leftmost column, the last cell in the sequence is in the rightmost column, and each pair of consecutive cells shares a common side.


The initial coloring of the grid is such that there is at least one left-to-right path. You are given this initial coloring as a String[] board with two elements. For each i and j, board[i][j] is either '#' (representing a black cell) or '.' (representing a white cell).


Snuke may color some of the white cells black. After he does so, there must still be at least one left-to-right path left on the board. The goal of the game is to color as many cells black as possible. Compute and return the largest number of cells Snuke can color black. (Note that the cells that are already black do not count.)

Definition

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

Constraints

  • board will contain 2 elements.
  • Each element in board will contain between 1 and 50 characters, inclusive.
  • All elements in board will have the same length.
  • Each character in board will be '#' or '.'.
  • The grid described by board will contain a left-to-right path.

Examples

  1. {"#...." ,"...#."}

    Returns: 2

    Snuke can color at most two white cells black. One possible final state of the board looks as follows: #.... ..###

  2. {"#" ,"."}

    Returns: 0

    Snuke can't color any cells.

  3. {"." ,"."}

    Returns: 1

  4. {"....#.##.....#..........." ,"..#......#.......#..#...."}

    Returns: 13

  5. {"." ,"#"}

    Returns: 0

  6. {".","."}

    Returns: 1

  7. {".","#"}

    Returns: 0

  8. {"..",".."}

    Returns: 2

  9. {"..",".#"}

    Returns: 1

  10. {"..","#."}

    Returns: 1

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

    Returns: 3

  12. {"...",".#."}

    Returns: 2

  13. {"..#","#.."}

    Returns: 0

  14. {"...",".##"}

    Returns: 1

  15. {"#.#","..."}

    Returns: 1

  16. {"...","###"}

    Returns: 0

  17. {"##.","..."}

    Returns: 1

  18. {"#","."}

    Returns: 0

  19. {"..","#."}

    Returns: 1

  20. {"..#","..."}

    Returns: 2

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

    Returns: 1

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

    Returns: 1

  23. {"......","##...."}

    Returns: 4

  24. {".......","..##..."}

    Returns: 5

  25. {".......#",".##..#.."}

    Returns: 3

  26. {"####..#..","........#"}

    Returns: 2

  27. {".#........","...##....."}

    Returns: 6

  28. {"#..........","....####..."}

    Returns: 5

  29. {"#..###......",".......#..#."}

    Returns: 5

  30. {"#........#...","..##..##....."}

    Returns: 5

  31. {"###..#..###...",".............."}

    Returns: 7

  32. {"...............",".#....#.#.#...."}

    Returns: 11

  33. {"###.......#.....","....#..........."}

    Returns: 9

  34. {"...#.#......#....","........#........"}

    Returns: 11

  35. {"............#....#","..##.....#........"}

    Returns: 12

  36. {"....#....#.........","#.....##...###....."}

    Returns: 7

  37. {"##..................",".....#.#........#..."}

    Returns: 14

  38. {"#....##...##..#......","........#...........#"}

    Returns: 10

  39. {"..#..#.....####.#.##..","#.......##............"}

    Returns: 7

  40. {"......#....#...#..###..","#####...##...#........#"}

    Returns: 2

  41. {"...###..#......##...####","..........#.......#....."}

    Returns: 8

  42. {".............#.#.......#.","#........#..............."}

    Returns: 19

  43. {"..............###.........","...#..#####.#......##..##."}

    Returns: 10

  44. {".......#...................",".........#.....#.#........."}

    Returns: 22

  45. {"#.....#....####.............","...##...##.......#.#..##.##."}

    Returns: 7

  46. {"#.........................##.","..###...#....#.#.....#.#....."}

    Returns: 16

  47. {"##....#..#...###........#..##.","...........#.........##......."}

    Returns: 13

  48. {".......#...#..............#....",".#..#....#....#..#..#.......#.#"}

    Returns: 14

  49. {".#..................#.....##....","...#..##..##.....#.....##......."}

    Returns: 16

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

    Returns: 16

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

    Returns: 8

  52. {".#....#..#......#..#........#.....#","...#...................#..........."}

    Returns: 22

  53. {"#...#........#....###...#........#..",".......#.......##..............#...."}

    Returns: 18

  54. {"..#.#...#.....................#......","#.....#....#...#...#.#............##."}

    Returns: 19

  55. {".....###......#..........####..#..###.","####.....####...###....#.............."}

    Returns: 9

  56. {"####.##.#....#...#.......#..#....#.....","..........##...#...#.###.............#."}

    Returns: 12

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

    Returns: 24

  58. {"........#........#...................#.##","....#.....###..#.......#..#.####.###....."}

    Returns: 17

  59. {"#.............##...#.#..............#.....","...#....##.......#.......#........#...##.."}

    Returns: 21

  60. {"....#..#....##....#.###.........##.........","..........#....##........#...#.......#.#..."}

    Returns: 19

  61. {"...#..............#######...#..########.....","##...#..##..##..#.........#.............##.."}

    Returns: 10

  62. {"..#....#.##.#.......#............##.#.......#","..............#...#...#......................"}

    Returns: 28

  63. {"...#...........##......#.....######........##.","##...#..###..#....##.....###.................."}

    Returns: 15

  64. {"#..#......#....#.................#.....##....#.",".....##......#...#.#.#.#.....#......#.........."}

    Returns: 22

  65. {".........#........#.#.#...............#....#....","##....#.....#...#..........#...#.#......#......."}

    Returns: 26

  66. {".............#............#.##...##...#.#...#...#","....#.#.........#..#....#.....................#.."}

    Returns: 28

  67. {".#..................#...........#...#....#......#.",".....#....##.....##...#....###....#....#....#....."}

    Returns: 22

  68. {".........................","........................."}

    Returns: 25

  69. {"..................................................",".................................................."}

    Returns: 50

  70. {"....#.##.....#...........", "..#......#.......#..#...." }

    Returns: 13

  71. {"###............................##.................", "....######.....###############....################" }

    Returns: 5

  72. {".", "#" }

    Returns: 0

  73. {"#..", "..#" }

    Returns: 0

  74. {"..", ".." }

    Returns: 2

  75. {"#.#", "..." }

    Returns: 1

  76. {"............#...", "................" }

    Returns: 15

  77. {"#....", "...#." }

    Returns: 2

  78. {"#...#", "..#.." }

    Returns: 0

  79. {".....#...................#........................", ".............#....#....#.........................#" }

    Returns: 41

  80. {"..................................................", ".................................................." }

    Returns: 50

  81. {".#..", "...#" }

    Returns: 1

  82. {"#...#...", "..#....#" }

    Returns: 1

  83. {"................#...............", ".....................#.........." }

    Returns: 29

  84. {"#...", "...#" }

    Returns: 1

  85. {"...", "..." }

    Returns: 3

  86. {"#.#..", "....#" }

    Returns: 1

  87. {".#.", "..." }

    Returns: 2

  88. {"....", "...." }

    Returns: 4

  89. {"...##", "##..." }

    Returns: 0

  90. {"...#", "#..." }

    Returns: 1

  91. {".#", ".." }

    Returns: 1

  92. {".....", "#####" }

    Returns: 0

  93. {".................................................", "................................................." }

    Returns: 49

  94. {"##...#", "...#.." }

    Returns: 0

  95. {"#...#..", "..#...#" }

    Returns: 0

  96. {"###", "..." }

    Returns: 0

  97. {".#.#.#.", "......." }

    Returns: 4

  98. {"#", "." }

    Returns: 0

  99. {"....#", "....." }

    Returns: 4

  100. {".", "." }

    Returns: 1

  101. {"..", "#." }

    Returns: 1

  102. {"..#", "..." }

    Returns: 2

  103. {"..#......#.......#..#....", "....#.##.....#..........." }

    Returns: 13

  104. {"..#.", "...." }

    Returns: 3

  105. {"...#...", "......." }

    Returns: 6

  106. {"...#...#..", ".....#...." }

    Returns: 5

  107. {"##...#..", "...#...." }

    Returns: 2

  108. {".#...", "...#." }

    Returns: 2

  109. {".##..", "....." }

    Returns: 3

  110. {"..#....", "....#.." }

    Returns: 4

  111. {"..#..", "....." }

    Returns: 4

  112. {"..###.....###...", "......###......." }

    Returns: 5

  113. {"....#.##.....#..........#", "..#......#.......#..#...." }

    Returns: 11

  114. {"...#......", ".........." }

    Returns: 9

  115. {"...#", "...." }

    Returns: 3

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: