JOIN
Get Time

   Problem Statement  

 Problem Statement for FoxAndGo3

Problem Statement

    Fox Ciel is playing Go with Jiro. Ciel plays black and Jiro plays white. You are given a String[] board that represents a square board on which they play. Black pieces are denoted 'x', white pieces 'o' and empty cells '.' (period).





In the current position no two white pieces are adjacent. Jiro has already given up and he will not be making any more moves. Ciel is considering making some more moves. Her goal now is to maximize the number of empty cells on the board.





In each move, Ciel can add a black piece onto an empty cell. After each move, all dead white pieces are removed from the board. A white piece is considered dead if its cell does not share a side with any empty cell.





Return the maximum number of empty cells on the board, after Ciel makes zero or more moves as described above.
 

Definition

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

Notes

-The rules described in the statement are not identical with the rules of Go. In particular, black pieces never die in this problem.
 

Constraints

-n will be between 3 and 50, inclusive.
-board will contain exactly n elements.
-Each element in board will contain exactly n characters.
-Each character in board will be one of 'o', 'x', and '.'.
-No two white pieces will be adjacent.
-Each white piece will be adjacent to at least one empty cell.
 

Examples

0)
    
{"o.o",
 ".o.",
 "o.o"}
Returns: 5
The best solution is to put black pieces on (1,2), (2,1), (2,3), and then on (3,2). After that the board will look as follows:
.x.
x.x
.x.
There are 5 empty cells.
1)
    
{"...",
 ".o.",
 "..."}
Returns: 8
This time the best solution is don't do any move.
2)
    
{"xxxxx",
 "xxoxx",
 "xo.ox",
 "xxoxx",
 "xxxxx"}
Returns: 4
3)
    
{".xox.",
 ".o.ox",
 "x.o.o",
 "ox.ox",
 ".ox.."}
 
Returns: 12
4)
    
{"o.o.o",
 ".ox..",
 "oxxxo",
 "..x..",
 "o.o.o"}
Returns: 12
5)
    
{"...",
 "...",
 "..."}
Returns: 9

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 594 Round 1 - Division I, Level Two