TopCoder problem "LineOfSight" used in TCHS SRM 11 (Division I Level Two)

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

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

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.)

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

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

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

Returns: 8

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

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

Returns: 4

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

Returns: -1

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6615

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10063&pm=6615

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Brute Force, Simple Search, Iteration