Statistics

Problem Statement for "LineOfSight"

Problem Statement

You are playing a game with some friends. The game is played on a rectangular chess board where each cell may be either empty or occupied by a rook. You are given a String[] board representing the layout of the board. Each character of each element of board represents a single cell of the board. A '.' represents an empty cell, while a 'X' represents an occupied cell.

The goal of the game is to take turns placing rooks onto empty spaces of the board so that they are not within the line of sight of any other rook. The line of sight extends directly up, down, left, and right.

Your strategy is to place your next rook on the board so that the number of "safe" squares remaining on the board (those that are not within the line of sight of any existing rook) is minimized, while also making sure that your piece is not within the line of sight of any rook already on the board. Return the number of safe squares remaining after you make the best possible move. If it is impossible for you to make a move on a safe square, return -1.

Definition

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

Notes

  • The placement of rooks already on the board may already include some that are within the line of sight of each other.

Constraints

  • board will contain between 1 and 50 elements, inclusive.
  • Each element of board will contain between 1 and 50 characters, inclusive.
  • Each element of board will have the same number of characters.
  • Each character of each element of board will be either '.' or uppercase 'X'.

Examples

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

    Returns: 16

    Picking the center square is one of the best options here. The resulting board looks like this (with the 'o' representing an unsafe cell): ..o.. ..o.. ooXoo ..o.. ..o.. (In this case, there is more than one way to get the minimum number of safe cells.)

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

    Returns: 1

    First, we need to consider which squares are safe. Consider the line of sight for the unit already there: Xoo o.. o.. Now, notice that any safe square can see the two of the others, so there will be exactly one safe square after we make our move.

  3. {"...", ".X.", "..."}

    Returns: 1

    On such a small board, the middle is a good location. The corners are the only safe moves. By the symmetry of the board, we know that each is equally good.

  4. {"...X...", ".X.....", ".......", ".......", "......."}

    Returns: 8

    We need to consider multiple units that have already been placed.

  5. {"....X", ".....", ".....", ".....", "X...."}

    Returns: 4

  6. {"..............................................","..............................................",".................X............................","..............................................","..............................................","..............................................","........................................X.....","..............................................",".............................................X","..............................................","..............................................","..X...........................................","...........................................X..","..............................X......X........",".X............................................",".....................X........................","...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: 342

  7. {"............................................",".................X..................X.......",".......................X....................",".......X....................................","............................................","............................................","......................X...X.................","..........X.....X....X......................","....X.......................................","............................................","...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: 198

  8. {"......X.........X................","..........X......................","X......................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: 270

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

    Returns: 238

  10. {".......................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.............................","...................................","..................................."}

    Returns: 294

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

    Returns: 170

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

    Returns: 196

  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..................","........................................."}

    Returns: 266

  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: 304

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

    Returns: 378

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

    Returns: 195

  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...",".............................",".............................","............................."}

    Returns: 240

  18. {".......................................","....................X..................","...............................X.......",".......................................",".......................................","................................X......",".......................................","..X..................................X.",".......................................","..................XX................X..",".......................................",".....X.............X...................",".......................................",".......................................","..........X............................",".......................................","........................X..............","............X..................X.......",".................X.....................",".............X........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: 187

  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.................","..........................................."}

    Returns: 135

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

    Returns: 276

  21. {"..................X.......","....X.....................","..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: 243

  22. {"..........................","..........................","..........................","..........................",".........X................","...X......................","................X.X.......","..........................","..........................","..........................","..........................","........................X.","..........................","..........................","..........................",".......................XX.",".......X...............X..","..........................","............X.............","....X...................X.","...................X......","..........................",".X........................","....................X.....","..........................","..........................","...............X..........",".........................."}

    Returns: 180

  23. {"........................................","........................................","..........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..............."}

    Returns: 240

  24. {"..........................X............",".............................X.........","...................................X...","..............................X........",".......................................","...................................X...","...............X.......................",".......................................",".......................X...X...........","...X.................X.................",".......................................",".....................X...............X.","..................X....................","..........X............................",".........................X.............",".......................................","......X................................",".......................................","................X......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: 221

  25. {"..............X..................",".................................",".................................","...............X.................","................................X","....................X............",".....................X...........","...................X.............",".............................X...",".................................","..........................X......","...................X.............","....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: 171

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

    Returns: 5

  27. {".......",".......",".......","...X...","X...X..",".......",".X.....","...X...","......."}

    Returns: 8

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

    Returns: 42

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

    Returns: 8

  30. {".......",".......",".......",".......","..XX...","......."}

    Returns: 16

  31. {"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}

    Returns: -1

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

    Returns: -1

  33. {".........X..........X.....","XXXXXX....................",".....XXXXX................","XXXXXXXXXXXXXXXXXXXXXXXX.X",".........X................","...X......................","................X.X.......","..........................","..........................","..........................","..........................","........................X.","..........................","..........................","..........................",".......................XX.",".......X...............X..","..........................","............X.............","....X...................X.","...................X......","..........................",".X........................","....................X.....","..........................","..........................","...............X..........",".........................."}

    Returns: -1

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

    Returns: -1

    These three rooks have the entire board within their site, so there is no move that can be made.

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

    Returns: -1

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

    Returns: -1

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

    Returns: -1

  38. {"......................................." }

    Returns: 0

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

    Returns: 1645

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

    Returns: 4

  41. {"XX.", "XX.", "..." }

    Returns: 0

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

    Returns: 0

  43. {"..XX", "..XX", "...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: