JOIN
 Problem Statement
Contest: 2012 TCO Marathon Round 1
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.