JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 75
Problem: BlackAndWhiteGame

Problem Statement

    BlackAndWhite is a game played by moving black and white tiles on a square board of size SZ * SZ. There are SZ * SZ + 1 tiles in the game, SZ * SZ of them are placed on the cells of the board, and the last one is held by the player. On each turn, the player shifts all tiles of a selected row/column by one cell in the selected direction, puts the tile he holds onto the cell which emptied after the shift and picks up the tile which got pushed out of the board. The goal of the game is to arrange the tiles on the board so that all white tiles are on the board (the player holds a black tile) and they all form a single 4-connected region. Your task is to find a way to reach this goal using as few shifts as possible.

You have to implement a single method makeConnected which provides you the initial layout of the tiles on the board as a String[] board. board[r][c] gives the color of the tile placed in row r and column c: 'X' for white or '.' for black. The tile held by the player initially is black.

This method should return the sequence of shifts the player should do to arrange the white tiles into a 4-connected group, formatted as follows. Each element of the return describes a single shift and is formatted as "row col" (without quotes). To perform this shift, the player's tile is placed at one end of the row or column which will be shifted, in a cell with coordinates (row, col). After this the whole row or column is shifted by one cell, so that the placed tile gets shifted into the board, and the cell on the other end of the row/column moves outside of the board. On the image the player's tile is black and it is used to shift the middle column down.



The shifts are performed in the order in which they are given in the return. Each shift description must be valid: either row or col must be -1 or SZ, and the other coordinate must be between 0 and SZ-1, inclusive. After all shifts white tiles must form a 4-connected group: for any pair of white tiles there must exist a chain of white tiles which connects them, and consecutive tiles in the chain should be adjacent on the board (vertically or horizontally).

The score for a test case will be 100 * max(0, 1 - (number of shifts in your return) / (SZ*SZ)). Invalid returns or returns which result in non-connected group of white tiles result in 0 score for that test case. The overall score is calculated as a sum of individual scores for all test cases.

The test cases are generated as follows. The size of the board SZ is chosen between 20 and 100, inclusive. Then the board is filled with black tiles, and a region of white tiles is chosen randomly as a rectangle (in 2/3 of the cases) or a stripe (in 1/3 of the cases) so that the number of white tiles is between 5% and 40% of the total number of tiles on the board. Finally, the rows and columns of the board are shifted randomly, so that each shift modifies the layout of the board. For the details of test case generation see the visualizer (method generate is responsible for this).

A visualization tool is provided for offline testing. It also allows manual play.
 

Definition

    
Class:BlackAndWhiteGame
Method:makeConnected
Parameters:String[]
Returns:String[]
Method signature:String[] makeConnected(String[] board)
(be sure your method is public)
    
 

Notes

-The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code).
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 100 full submission test cases.
 

Examples

0)
    
Seed = 1
Grid size = 20
....................
....................
....................
................X...
.................X..
X...............XXX.
...............X.XX.
.................X.X
....................
....................
..............XX....
............X.X.....
...............XXX..
................X...
X...............X.X.
...............X....
....................
..............X.....
....................
....................
1)
    
Seed = 2
Grid size = 74
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................X...............................................
.........................X................................................
.....................X.X.X.XX.............................................
...................X.XX.XXX.XX.X..........................................
..................XX.X.XXXXXX.............................................
..................XXXXXXXXXX..............................................
............X...XXXXXXXXXXXXX.X...........................................
...............XX..XXXXXXXXX.X..X.........................................
...............XXXXXXXXXXXXXXX............................................
................XXXXXXXXXXX...............................................
...........X.....XX..XXXXXXXXXXX..XX......................................
...................XXXXXXXXXXXX...........................................
.................X.XXXXXXXXXXX.XXX........................................
.................X.XXXXXXXXXXXXX.X........................................
..................X.XXXXXXXXXXXX..........................................
................XXX.XXXXXXXXXXX.XX........................................
..............XXXXXXXXXXXXXX...X..........................................
.................X.XXXXXXXXXXX....X.......................................
................X.XXXXXXXXXXXX.X..........................................
................XXXXXXXXXXXXXX............................................
...............XXXXXXXXXXXXXX.............................................
.............X...XXXXXXXXXXXXX............................................
...............XXXXXXXXXXXXXXXX...........................................
................X.XXXXXXXXXXXX............................................
.................X..XXXXXXXXXXX...........................................
..................XXXXXXXXXXXXX...........................................
....................XXXXXXXXXXXX..........................................
................XXXXXXXXXXXXXXXXX.........................................
................X.XXXXXXXXXXX...X.........................................
.................XXXXXXXXXXX.X.X..........................................
................X.XXXXXXXXXXXX.X..........................................
.................XXXXXXXXXXXXXX...........................................
...................XXXXXXXXXXXX...........................................
.................XXXXXXXXXXXX..XX.........................................
..............X..XXXXXXXXXXXXXX...........................................
...............XXXXXXXXXXXXXXXXXX.........................................
...............XXX.XXXXXXXXXXXX...........................................
.................X.XXXXXXX.XXXXX..........................................
.............XX.XXXXXXXXXXX...............................................
.............X.XXXXXXXXXXXXX..............................................
..................XXXXX..X.XXX............................................
................XX...XX...................................................
.................X.X..X.X....X............................................
............................XX............................................
..................X.......................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
2)
    
Seed = 3
Grid size = 78
.............X................................................................
..................X.......X...................................................
........X.....X.......X....X..................................................
...............X..X.XX........................................................
..........XX.......XXX......X.X...............................................
............XX..XXX..XX..X....................................................
.............X...XX...XXXX..X.....XX..........................................
.....X.X..XXX...XXX.XX.XXXXXXX....X...X.......................................
......XX...X.X.XX.XX.XX.XX.X........X....X....................................
...............XXX.XX.XXXXXXXXX..XX...........................................
.....X..X.XX..X.XXXXXXXXXXXXX..X.X.XXX...X..X................................X
........X..XXXXXXXXXX.XXXX.XXXXX.X............................................
.........X..XXX.XXXX.XXXXXXXXX.XX.XX......X...X...............................
............XXXXXX.XXXXXXXXX.XXXXX......X.....................................
.......XX.X.XXXXXXXXXXXXXXXXXX.X..XX....XX....................................
.......X..XX.XXXXXXXXXXXXXXX.X.XX....X.X......................................
.......X..XXXXXXXXXXXXXXXXX.XX.XX..X..........................................
........XXXX.XXXXXXXXX.XXXXXXXXX.XX.X.........................................
..X..XXXX.XXXXXX.XXXXXXXXXX.X.X...............................................
.....X.XX.XXXXXXXXXXXXXXX.XXX.XXXX...........................................X
..X......XXXXXXXXXX.XXXXXXX.XX.X..X...........................................
X......XXXXX.XXXXXXX.XXXXXXX.X......X.....X...................................
.....XXX.X..XX...X.XXX.XXX...XX..X..XX........................................
.......X.X.....X..XXX.XX.......X.XXX..XX......................................
..X......XX.X.XXX..XX.X....XXX.....X..........................................
......X...XXXX..X.X..X.XXX..XXXXX..X..........................................
.......X....XX.X...X..XX.X.XX.................................................
.....XX.X...........X.........X.XX.X.X........................................
......X.XX..X........X......X.................................................
.......X..XXX.........X.......X.X.............................................
.X...X........................................................................
.........X..X..........X.X..X.................................................
..........X..................X................................................
..............................................................................
...............................X..............................................
..............................................................................
..............................................................................
................................X.............................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
..............................................................................
.....................X........................................................
..............................................................................
3)
    
Seed = 4
Grid size = 41
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
...................................X.....
.........................................
................................X........
.................................X.......
................................XX..X...X
.................................X.X.....
...........................XX.X.X....X...
.............................X.X.XXX...X.
...........................X.XXXXXXX.....
.............................X.XXXX......
.............................XX.....XX...
............................X...XX.X..X..
............................XXXXXXXXX....
..............................XXX.XX.....
........................X.X..XXX.X.......
...........................X.XXXXX.......
...........................X.X.X.XXX.....
........................X...X..XXX..X....
...........................X.XXXX...X....
...........................X....XXX...X..
.............................X.X...X.X...
.............................X..XXX.X....
...........................X...XX.X..X...
..........................X....XX..XX..X.
................................XX.XX....
............................X.XXXXX.X....
................................XX.......
.................................X....X..
.........................................
.........................................
.........................................
4)
    
Seed = 5
Grid size = 43
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................................
...........................X...............
....................X....X.................
.......................X....X..............
................................X..........
.........................X.................
.........X............XX...X.X.............
..X......X.....X.X.X.XXXX.X.X..............
...X..X.X.............XX.X...X.......X.....
.......X.X...X..XXXX.XXXX.X.XXX...X........
...X......X.XX..X.XX.XXX..XX..X....X.......
.........X.XXXX.X.XXXX..X.XXX..XX.......X..
...X....XX.XXX.XXXXX....XXXXX.X............
....X...XX..X.X.XXXXXXXX.X.XXX.XXXX........
.....X.XX.X..XXXX.XX.XX.X..XX..............
......X.XXXXXXXX.XX.XX..XXX.X...X...X......
......XX.X.XX.XXX..XXX..X.X.X.XX.X.........
.......XXXX.XXXX.XXX.....X.X...............
...X..XX.XXX...X.XXX.XXX...................
.....X...XX..X.XX..X......X..X.............
..........XX..XX.X.XXXXXX.......X..........
....X..X...X...X.............X.............
...XX..........X.....X.....................
..........X....XX..........................
.................X..X.........X.X..........
.....................X.....................
......X.X......X...........................
...........................................
...........................................
...........................................
5)
    
Seed = 6
Grid size = 71
..........X............X...X.................X....X...X..X...........X.
.....................X.....................X...........................
...............X.......................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.......................................................................
.........................X........X....................................
.......................................................................
..................................X....................................
......................X.....X.XX.XXX....X.............................X
.X........................X...X..X...X.X........X......................
..........X.......X..XX.X...X.X.X.X.XX...X......X......................
..................X...X.X...X...XXXXXXX..X.......X.X...XX..............
.........XXX..X......XXX.X...X.XXXXXXXX.X.XX.XX.XXXX...X...............
..........X..XXXX.XXXX.XXXXXXXXXXXXXXXXXX.X...XX.XXXXXX..X..X..........
......X.X..X...XXXX..XXX.XXXX.XXXX.XXXXX.XXX.XXXXXXXX.XX..X............
......XX...XXXXX..XXXXXXXXXXXXXXXX.XXXXXXXXX.XXXXXXXX.XX...............
.........X..XXXX.XXXXXXXXXXXXXXXX...XXXXXXX.XXXXXXXXXXX.XX.X...........
..............XXXXXXXXXXXXXXXXXXXXX.XXXXX.XXXXXXXXXXXXXX..X............
......X....XXXX.XXXXXXXXXX..XX.XXX.XX.XX.XXXXXX.XXX.X......X.X........X
......X.XX..XXXXXXXXXX.XX..XXXX...X..XXXXXXXXXXXXXX.XXXXXX.............
.............XXXX..X.X...XXX...XX..X.XX.X.XXXXXXXXX...XX.X.............
..X.......X.XX.X..XX.XXX....X.....X......XXX.X..X..XXX.................
......................X.X.X..X..X.....XX..X......XX...X..X............X
6)
    
Seed = 7
Grid size = 80
............X.X.XXXXXXXXXXXXXXXXX.......XX......................................
.........X...XXXXXXXXXXXXXXXXXXXX..X.X..........................................
............XXXXXXXXXXXXXXXXXXXXXXXX.XXXX.......................................
.X....X.X.XX.XXXXXXXXXXXXXXXXXXXXXX.XXX.........................................
...........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.....................................
.......X..XXXXXXXXXXXXXXXXXXXXXXXXXX.X........................................X.
X......X..X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X......................................
............XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.....................................
.............XXXXXXXXXXXXXXXXXXXXXXXXXXX....X...................................
..........XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX..X...................................
............XXXXXXXXXXXXXXXXXXXXXXXXXXX.X.......................................
.......X.XXX.XXXXXXXXXXXXXXXXXXXXXXXXX.XX.......................................
........X..X.XXXXXXXXXXXXXXXXXXXXXXXXXXX........................................
....X..X..XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X....................................X...
........X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................................
.........X.XXXXXXXXXXXXXXXXXXXXXXXXXXX.X........................................
........X.XXXXXXXXXXXXXXXXXXXXXXXXXXX.X.........................................
........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX...X.......................................
......XXX.XXXXXXXXXXXXXXXXXXXXXXXXX.XX..........................................
.........XXXX.XXXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
........X.X.XXXXXXXXXXXXXXXXXXXXXXXXX....X.....................................X
........XX.X..XXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X..................................X
.........X..XXXXXXXXXXXXXXXXXXXXXXXXXXX..X......................................
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................................
.........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXX......................................
.............XXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
X.X......X.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X....................................
..........XXXX.XXXXXXXXXXXXXXXXXXXXXXXXX........................................
...X....XXXX.XXXXXXXXXXXXXXXXXXXXXXXXX..XX......................................
........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....X....................................X
X.........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
...X....XX.XXXXXXXXXXXXXXXXXXXXXXXX.XXXX........................................
..........X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX......................................
XX......X..XXXXXXXXXXXXXXXXXXXXXXXXXXX.XX.......................................
...........XXX.XXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
.......X...XXXXXXXXXXXXXXXXXXXXXXXXX.XXXX.......................................
.........XX..XXXXXXXXXXXXXXXXXXXXXXXXXXX...X....................................
.........X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
..........X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.....................................
...........X..XXXXXXXXXXXXXXXXXXXXXXXXXXX.X.....................................
........XX..XXXXXXXXXXXXXXXXXXXXXXXXXX..X.......................................
...X..X..XXXXXXXXXXXXXXXXXXXXXXXXXXXX.XX........................................
...X......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................................
.......X..XXXXXXXXXXXXXXXXXXXXXXXXXX.X..X.......................................
.......X.XX.XXXXXXXXXXXXXXXXXXXXXXXXX..X........................................
.....X..X.XX.XXXXXXXXXXXXXXXXXXXXXXX.X..........................................
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.....................................
.........X.X.XXXXXXXXXXXXXXXXXXXXXXXXX.X........................................
.........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...X....................................
........XX.XXXXXXXXXXXXXXXXXXXXXXXXXX.X...X.....................................
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.......................................
........X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XX.X...................................X
.X...........XXXXXXXXXXXXXXXXXXXXXXXXXXXX..X....................................
......X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.........................................X
........X..XXXXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
X..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
X.......X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXX.X.....................................X.
..........X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX......................................X
......X....X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.......................................
X......X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXX.XXX......................................
.......X...X.XXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
.........XXXXXXXXXXXXXXXXXXXXXXXXXXX.XX..X.X....................................
.......X.XX.XXXXXXXXXXXXXXXXXXXXXXXXXX..XX......................................
.............XXXXXXXXXXXXXXXXXXXXXX.X.XX.....................................X..
..........XX.XXXXXXXXXXXXXXXXXXXXXXXXXX.X.....X.................................
..........XXXX.XXXXXXXXXXXXXXXXXXXXXXXXX..X.....................................
..........XXXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...................................
....X......XXXX.XXXXXXXXXXXXXXXXXXXXXXX.XX..X..X...............................X
X...X.XX......XXXXXXXXXXXXXXXXXXXXXXXXX..X....X.................................
.......X.....XXXXXXXXXXXXXXXXXXXXXXXXX.XXX..X...................................
X.........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X......................................
X........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.........................................
.......X.X.X.XXXXXXXXXXXXXXXXXXXXXX.X.XX.....................................X..
.X......X..XXXXXXXXXXXXXXXXXXXXXXXXXXXX..X......................................
...X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXX.XX...........................................
.X.....XXXX.X.XXXXXXXXXXXXXXXXXXXX..............................................
.X........XX.X.XXXXXXXXXXXXXXXXXXXXX.XX.X.......................................
.......X.XX...X..XXXXXXXXXXXXXXXX.XX.X..X..X....................................
7)
    
Seed = 8
Grid size = 24
......................X.
.............X..........
........................
.......XX......X.X..X...
........XXX...X..XX.....
......X.XX.X...XXXXXX.X.
.......XXXXX..XXXXX.X...
...X.XXXXXXXXXXXXXXXXX..
.......XXXXXXXXXXXXXXXX.
.....X.XXXXXXXXXXXXXXXX.
......XXXXXXXXXXXXXXXX.X
.......XXXXXXXXXXXXXXX..
........XXXXXXXXXXXXXXX.
........XXXXXXXXXXXXXXXX
.......XXXXXXXXXXXXXXXXX
.........XXXXXXXXXXXXXX.
.......X..XXXXXXXXXXXXX.
..........XXXXXXX.XXX.XX
.........XXXX.X...XXX.XX
.........X.XX......X.X..
............XX.......X..
........................
........................
........................
8)
    
Seed = 9
Grid size = 84
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
....................................................................................
.......X...........X................................................................
.....................X..............................................................
..........X.........................................................................
..........X......X....X.............................................................
.......X........XX.X................................................................
...........XX....X.......X..........................................................
.......XX.X.XXXX.X.XXX.XXXX.........................................................
....X.X..XXXXXXXXXXXXXX.............................................................
..........X.XXX.XX....XXXX..........................................................
.....XX..XXXXXXXX.XXXXXXXXX.........................................................
.........XXXXXXXX.XX.XXXXX.X..X.X...................................................
........XXXX..XXXXXXXXXXX.XXX.X.....................................................
.....X.X..XXXXXXXXXXXXXXX..X.X......................................................
....X..XXXXXXX.XXXXXXXXX.XXX........................................................
...........XXXXXXXXXXXXXXXXXX.......................................................
......X...XXXXXXXXXXXXXXX..X.XX.....................................................
........XXXXXXXXXXXXXXXXXXX.........................................................
.......XXX..XXXXXXXXXXXXXX.X........................................................
.........X.XXXXXXXXXXXXXXXX.........................................................
.......X.X.XXXXXXXXXXXXXXXX.XX......................................................
........XXXXXXXXXXXXXXXXXX.X...X....................................................
.......XX..X.XXXXXXXXX.XX.XX.X......................................................
..........XXXXXXXXXXXX.XX.XX........................................................
.....X.X.XXXXXXXXXXXXXXXXXX.X.......................................................
.......XXXXXXXXXXXXXXXXX.X.XX.......................................................
........XXXXXXXXXXXXXXXXXXXX........................................................
......XXXXXXXXXXXXXXXXXXXX..........................................................
.......X.XXXXXXXXXXXXXXXXXX.........................................................
.......X.XXXXXXXXXXXXXXXXXXX........................................................
.......XXXXXXXXXXXXXXXXXXX..X.......................................................
......X...XXXXXXXXXXXXXX..XX........................................................
.........XXXXXXXXXXXXXXXXXX.........................................................
........XX.XXXXXXXXXXXXX.XX.X.......................................................
........XXXXXXXXXXXXXXXXX...X.......................................................
.........XXX.XXXXX.XX.XXXXXX.X......................................................
.......XX.XXXXXXX.XXX.XXXXXX.X......................................................
...........XXXXX..X..XXXX..XX..X....................................................
.....X....X....X...XXX.X.XXX.X......................................................
...........X.XX.X.XXX..XXX..........................................................
..............X..XX.XX......X.......................................................
............X...X....X..............................................................
..................X.................................................................
.......................X.....X......................................................
....................................................................................
....................................................................................
9)
    
Seed = 10
Grid size = 87
.X.....................................................X....XX.X......X.....X.......X..
....................................................X...........XX.......XX.XX......X..
......................................................X...XX..XX..XXXX.X..X.....X....X.
..X........................................X..............X.XXXXXXX....XXX.XXX....X..X.
X........................................................X.X.XXXXXXXX.XXX.XXX.XX....X..
....X............................................X..X..X..XXXXXXXXX.X.XXXXXXX..XX.....X
.......................................................X.XXXXXXXXX.XXXXXXXXXXX.X....XXX
X......................................................XXXXXXXXXXXXXXXXXXXXX.X.X..X....
....................................................XX.XXXXXXX.XXXXXXXXXXXXXXXX.......X
.X...................................................X...XXXXXXXXXXXXXXXXXXX.XXXX..X...
.....X..............................................X.XXXXX.X.XXXXXXXXXXXXXX.XX.X...X.X
...................................................X.X....XXXXXXX.XX.XXXXXXXXXX.XX.....
............................................X......XX.XX.XXXXXXXXXXXXXXXXXX..X.X.XX....
.......................................................X.XXX.XXXXXXXXXXXXXXXXX.X......X
.......................................................XX.XXXXXXXXXXXXXXXXX.X.XXX.X....
...................................................X...X....XX.XXXXXXXXXXXX.X..X.XXXX..
.......................................................XXX.XXXXXXXXX.XX..XXXXXXX.......
..............................................X............XXXXXXXXXXXXXX..X.XXXX.X....
...X......................................................X..X.X.XXXXXXXX..XXX..X..X.X.
...................................................X..X..XXXXX.X.XXXXXX...XXX.X.XX....X
......................................................X.X...X..XXXXXXXXX.XXX..X.XXX..X.
.............................................X.X.....X....XXXXXXX.XXXX.......XXX.X.....
.......................................................X..X...XXXXXXX....X.XXX.XX....X.
X...................................................X.XX..X.X...XXXXX....XX.......X....
...................................................X.....X..XXXX...XX..X.X..X..X.X.....
..........................................................X..X.....XXX..X........X.....
............................................................XX.X.XXX...................
..............................................X..............X...XX..XX.....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
XX............................................X......X.................................

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.