Statistics

Problem Statement for "MultiplayerBattleships"

Problem Statement

Multiplayer Battleships is a game for playerCount players, who take turns one after another. The game field is a rectangular grid containing one or more battleships. A battleship of size p is a 1xp or px1 rectangle, where p is between 1 and 4, inclusive. No two battleships share a cell, a side or a vertex. Each cell of a battleship is called a deck.

In one turn, a player selects one unattacked deck of any battleship and attacks it. If this deck is the last unattacked deck of that battleship, the ship drowns and the player gets p points, where p is the original size of the ship (see example 2). Otherwise, if the ship contains more unattacked decks, the player gets 1 point instead. The game is over when all decks of all battleships have been attacked.

All players follow the same strategy, and each player knows that all the other players are also following this strategy. Each player is trying to maximize his score at the end of the game. If there is more than one ship that the player can attack to achieve the highest possible score, he will pick the one among them whose top-left corner is the highest (i.e., in the uppermost row). If there are still multiple such ships, he will choose the one among them whose top-left corner is farthest to the left (i.e., in the leftmost column).

You will be given the game field in a String[], where a '.' represents an empty cell and an uppercase 'X' represents a deck. Each element represents a single row, and the rows are given from top to bottom. The cells in each row are given from left to right. Return the maximal score that can be achieved by the first player.

Definition

Class:
MultiplayerBattleships
Method:
getFirstPlayerScore
Parameters:
String[], int
Returns:
int
Method signature:
int getFirstPlayerScore(String[] field, int playerCount)
(be sure your method is public)

Constraints

  • field will contain between 1 and 7 elements, inclusive.
  • Each element of field will contain exactly m characters, where m is between 1 and 7, inclusive.
  • Each character in each element of field will be either uppercase 'X' or '.'.
  • playerCount will be between 1 and 16, inclusive.
  • field will contain a valid game field.
  • field will contain at least one battleship.

Examples

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

    2

    Returns: 1

    The first player attacks one deck for a total of 1 point. The second player will then attack the remaining deck and get 2 points.

  2. {".XXXX.."}

    3

    Returns: 5

    The first player gets two turns. On the first turn, he attacks one deck for 1 point. On the second turn, he attacks the last remaining deck for 4 points.

  3. {".XX", "...", "XXX"}

    2

    Returns: 6

    Hit the bottom ship first.

  4. {"XXXX", "....", "XXXX", "....", "XXXX", "....", "XXXX"}

    3

    Returns: 12

  5. {"X"}

    1

    Returns: 1

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

    8

    Returns: 4

  7. { "XX.XX.X", ".......", "XX.XX.X", ".......", "XX.XX.X", ".......", "XX.XX.X" }

    2

    Returns: 10

  8. { "XX.XX.X", ".......", "XX.XX.X", ".......", "XX.XX.X", ".......", "XX.XX.X" }

    16

    Returns: 3

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

    3

    Returns: 10

  10. {"XXXX","...."}

    2

    Returns: 2

  11. {"XXXX.X.",".......","X.XXX.."}

    3

    Returns: 6

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

    4

    Returns: 1

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

    5

    Returns: 3

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

    1

    Returns: 7

  15. {"X....","X....","X..XX","X....",".....",".....",".XXXX"}

    2

    Returns: 5

  16. {"X"}

    3

    Returns: 1

  17. {"XXX.","...."}

    4

    Returns: 1

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

    5

    Returns: 2

  19. {".XX","...","...","XXX"}

    1

    Returns: 8

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

    2

    Returns: 5

  21. {"XX","..","X.","X.","X.","X."}

    3

    Returns: 2

  22. {".....",".....","XXXX.",".....",".X...",".X..X",".X..X"}

    4

    Returns: 6

  23. {"X"}

    5

    Returns: 1

  24. {"....","XXXX"}

    1

    Returns: 7

  25. {"X..XXXX","X......","X.XXXX."}

    2

    Returns: 14

  26. {"...","...","X.X","X.X"}

    3

    Returns: 3

  27. {".....X",".XX..X",".....X","X.....","..XXXX"}

    4

    Returns: 3

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

    5

    Returns: 5

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

    1

    Returns: 19

  30. {"X"}

    2

    Returns: 1

  31. {"....","XXXX"}

    3

    Returns: 5

  32. {"XXX.X.X","......X",".XXXX.X"}

    4

    Returns: 5

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

    5

    Returns: 2

  34. {"X.XXXX","......",".XXXX.","......",".XXXX."}

    1

    Returns: 22

  35. {"X.","..",".X",".X",".X",".."}

    2

    Returns: 2

  36. {".XXX.",".....",".....","..XXX",".....","..XXX","....."}

    3

    Returns: 5

  37. {"X"}

    4

    Returns: 1

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

    5

    Returns: 1

  39. {"......X","XXXX..X","......X"}

    1

    Returns: 12

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

    2

    Returns: 3

  41. {"......",".X.XXX",".X....",".....X","XXXX.X"}

    3

    Returns: 5

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

    4

    Returns: 1

  43. {".XXX.",".....",".....",".XXX.",".....",".XXXX","....."}

    5

    Returns: 4

  44. {"X"}

    1

    Returns: 1

  45. {"....","XXXX"}

    2

    Returns: 2

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

    3

    Returns: 2

  47. {"X.X","X.X","X.X","X.X"}

    4

    Returns: 2

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

    5

    Returns: 5

  49. {"..","X.","X.","X.","X.",".."}

    1

    Returns: 7

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

    2

    Returns: 4

  51. {"X"}

    3

    Returns: 1

  52. {"....","XXXX"}

    4

    Returns: 1

  53. {"X.XXXX.","X......","X..XXX."}

    5

    Returns: 2

  54. {".X.",".X.",".X.","..."}

    1

    Returns: 5

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

    2

    Returns: 15

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

    3

    Returns: 3

  57. {".X...",".X...",".X...",".X.XX",".....",".X...",".X..."}

    4

    Returns: 3

  58. {"X"}

    5

    Returns: 1

  59. {"XXXX","...."}

    1

    Returns: 7

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

    3

    Returns: 10

  61. {".......","..XXXX.",".......",".....XX",".......","...X...","...X..."}

    2

    Returns: 4

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

    5

    Returns: 7

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

    3

    Returns: 13

  64. {".......","XX..X..",".......",".....X.","...X...",".......","..X...."}

    3

    Returns: 2

  65. {".......",".......","....X..","....X..","..X.X..","..X.X..","......."}

    4

    Returns: 2

  66. {".......",".XXX...",".......","...XX..",".......",".XXXX..","......."}

    3

    Returns: 5

  67. {"X......","...XX..",".......","X.X.X..",".......",".......","......."}

    2

    Returns: 3

  68. {"..XXXX.",".......","..XXXX.",".......",".......","..XXX.X","......X"}

    3

    Returns: 9

  69. {"...X...",".......","X......","..XX..X",".......","X..X...","......."}

    5

    Returns: 2

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

    2

    Returns: 24

  71. {"..XXX..","X......","X......","X....X.",".....X.",".....X.",".....X."}

    3

    Returns: 9

  72. {"X....XX","X.X....","..X.XX.","X.X....","X...X.X","X.X.X.X","X.X.X.X"}

    5

    Returns: 9

  73. {".....XX",".X.X...",".X....X",".X..X..",".......",".....X.","XXXX.X."}

    2

    Returns: 7

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

    2

    Returns: 9

  75. {"...XXXX",".......",".X.....",".X.....",".X.XXX.",".X.....","...XXXX"}

    2

    Returns: 19

  76. {".......",".......","...X...",".......",".......",".......","......X"}

    3

    Returns: 1

  77. {"..XXXX.","X......","X.XXXX.","X......","X..X.X.","...X.X.","XX.X.X."}

    2

    Returns: 10

  78. {".......",".XX...X","......X",".......",".......",".......","......."}

    2

    Returns: 2

  79. {"....XX.",".X.....",".X....X",".X..X..","....X.X","..X.X.X","X...X.X"}

    5

    Returns: 6

  80. {"...XX..",".......",".X.....",".X..XX.",".......","....X.X","......."}

    2

    Returns: 4

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

    7

    Returns: 7

  82. {".......",".......",".......",".XX....",".......",".......","......."}

    5

    Returns: 1

  83. {".......","..X....","..X.XX.",".......","..XXXX.",".......","......."}

    2

    Returns: 4

  84. {".XXXX..","......X","..X....","..X....","..X.X.X","....X.X",".XX.X.X"}

    4

    Returns: 7

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

    16

    Returns: 1

  86. {"XXX.XXX",".......","XXX.XXX",".......","XXX.XXX",".......","XXX.XXX"}

    16

    Returns: 2

  87. {"X"}

    2

    Returns: 1

  88. { "XX.XX.X", "......X", "XX.XX..", "......X", "XX.XX.X", ".......", "XX.XX.X" }

    16

    Returns: 3

  89. { ".......", ".......", ".......", ".......", ".......", "...X...", "......." }

    16

    Returns: 1

  90. { ".X.....", ".......", ".......", ".......", ".......", ".......", "......." }

    1

    Returns: 1

  91. {"XXX.XXX", ".......", "XXX.XXX", ".......", "XXX.XXX", ".......", "XXX.XXX" }

    1

    Returns: 40

  92. {"XXX.XXX", ".......", "XXX.XXX", ".......", "XXX.XXX", ".......", "XXX.XXX"}

    16

    Returns: 2

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

    16

    Returns: 2

  94. {"..X", "..X", "...", "X.X" }

    3

    Returns: 2

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: