Diana has been arrested for endangering diligent computer science students with her negligence on making test cases, and thrown into juvenile detention! The jail is an by bit image, with X
representing a wall and .
representing an empty space. A group of empty spaces that have adjacent sides will make up a jail cell. The entire jail complex will be surrounded by X
on its borders. Here is a sample jail complex with four jail cells:
XXXXXXXX
X..XXXXX
X.X....X
XX.XXXXX
X...XX.X
X.X..XXX
X......X
XXXXXXXX
While in juvie, Diana pulled a Shawshank Redemption and befriended all of the other computer scientists that are being detained at the complex, one in each cell. She also dug a hole in her cell, which reaches down into the sewers, and plans to escape through this hole. However, she doesn't want to leave behind her new friends, and wants to break down the least number of walls (that is, change the least number of X
to .
) such that all cells will become connected to each other. This way, all of her friends can travel to her cell and escape down her hole.
She uses her one free phone call to phone Jeffrey, and asks him to help her figure out which walls to break such that the least number of walls are broken. While Jeffrey is busy developing an algorithm to answer this problem, Diana decides to get a head start and wants to figure out which wall to break in order to connect the most number of cells! She decides to break only one wall for now.
In order to keep track of the cells, Diana decides to number them based on their parent position. Diana defines the parent position of a jail cell to be the top most position with a .
, and ties for the parent position will be broken by choosing the left most .
. The cells will be numbered from to from top to bottom depending on their parent position. Ties between numbering jail cells will be broken by choosing the left most parent position.
For example, here is the above jail complex with numbered cells:
XXXXXXXX
X11XXXXX
X1X2222X
XX3XXXXX
X333XX4X
X3X33XXX
X333333X
XXXXXXXX
Input Specification
On the first line will be two integers, and , the number of rows and the number of columns in the jail complex respectively. The next lines each have characters, either X
, denoting a wall, or .
, denoting an empty space.
Output Specification
On the first line, print the maximum number of cells that Diana can connect by breaking just one wall.
On the second line, print two space separated integers and , denoting the position of the wall to break. The ordered pair will denote the position at the column and the row. The top left corner of the jail cell is located at .
On the final line, print the numbers of all jail cells that become connected by breaking that wall, in increasing order.
If no jail cells can be connected by breaking only one wall, print out only the integer -1
, and none of the three lines listed above.
If multiple walls can result in the same number of connected jail cells, print the top-most wall. If there are further ties between walls to break, choose the left-most wall.
Sample Input 1
8 8
XXXXXXXX
X..XXXXX
X.X....X
XX.XXXXX
X...XX.X
X.X..XXX
X......X
XXXXXXXX
Sample Output 1
3
2 2
1 2 3
Sample Input 2
21 72
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX............XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX............XXX
XXX............XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX............XXX
XXX............XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX............XXX
XXX...XXXXXXXXXXXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX...XXXXXXXXXXXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX...XXXXXXXXXXXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX...XXX......XXXXXX...XXXXXXXXXXXXXXX............XXXXXX.........XXXXXX
XXX...XXX......XXXXXX...XXXXXXXXXXXXXXX............XXXXXX.........XXXXXX
XXX...XXX......XXXXXX...XXXXXXXXXXXXXXX............XXXXXX.........XXXXXX
XXX...XXXXXX...XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX...XXXXXX...XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX...XXXXXX...XXXXXX...XXXXXXXXXXXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX............XXXXXX............XXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX............XXXXXX............XXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXX............XXXXXX............XXXXXX...XXXXXX...XXXXXX...XXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Sample Output 2
-1
Comments
What is the maximum amount of cells total?
With the maximum number of cells, the jail complex will end up looking like a checkerboard.
Let's say .
Just a reminder that the output order is (x, y), where x is column and y is row. Don't output (row, col) as me :-)