This is the third problem of google code jam qualification round 2014. This problem is based on very famous old game Minesweeper, i am pretty much sure you must have played it, its now time to create the board yourself, such that you know the position to click on, to win the game in just one click.
Problem
Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.
In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don’t contain mines have been revealed, the game ends, and you win.
For example, an initial configuration of the board may look like this (‘*’ denotes a mine, and ‘c’ is the first clicked cell):
*..*...**. ....*..... ..c..*.... ........*. ..........
There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:
*..*...**. 1112*..... 00012*.... 00001111*. 00000001..
At this point, there are still un-revealed cells that do not contain mines (denoted by ‘.’ characters), so the player has to click again in order to continue the game.
You want to win the game as quickly as possible. There is nothing quicker than winning in one click. Given the size of the board (R x C) and the number of hidden mines M, is it possible (however unlikely) to win in one click? You may choose where you click. If it is possible, then print any valid mine configuration and the coordinates of your click, following the specifications in the Output section. Otherwise, print “Impossible”.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated integers: R, C, and M.
Output
For each test case, output a line containing “Case #x:”, where x is the test case number (starting from 1). On the following R lines, output the board configuration with C characters per line, using ‘.’ to represent an empty cell, ‘*’ to represent a cell that contains a mine, and ‘c’ to represent the clicked cell.
If there is no possible configuration, then instead of the grid, output a line with”Impossible” instead. If there are multiple possible configurations, output any one of them.
Limits
0 ≤ M < R * C.
Small dataset
1 ≤ T ≤ 230.
1 ≤ R, C ≤ 5.
Large dataset
1 ≤ T ≤ 140.
1 ≤ R, C ≤ 50.
Sample
| Input | Output |
5 5 5 23 3 1 1 2 2 1 4 7 3 10 10 82 |
Case #1: Impossible Case #2: c . * Case #3: Impossible Case #4: ......* .c....* ....... ..*.... Case #5: ********** ********** ********** ****....** ***.....** ***.c...** ***....*** ********** ********** ********** |
Solution:
Its important to understand the location of c first.
As we need to win it in one click all the dots should be interlinked and clicking on any dot with 0 value will work, so c can be replaced by any dot which is having 0 mines in its surrounding.
Also its important to understand that if we keep dots on the edge it is more easier to form the board which can be win in one click, as the condition 0 can be met easily, same number of dots inside the board will not form more zeros then if they are on the edge. So we will try to keep the dots on the edges.
We can deduce the problem in these 4 cases
Case 1: Only one dot remaining all mines
This is straightforward, keep first location as dot and remaining all mines
. * * *
* * * *
* * * * , here dot can be replace by c.
Case 2: boad has only one column or one row
in this case we can keep all dots consecutively and all mines(*) consicutely.
ex 1 . . . . . . . * * * * * and c can be at first location
ex 2 .
.
.
.
*
*
* Here also c can be at first location.
Case 3: When board has two columns or two rows
in this case we can arrange dots in pait of 2’s
. .
. .
* *
* *
OR
. . . * *
. . . * *
If number of dots are in even numbers, we can not win the board in one click.
Case 4: When board has more than two columns and two rows
in this case atleast 4 dots are required in this way
. .
. .
Now if we get 5th dot then it is not possible to win in one click
ex:
. . .
. . *
* * *
6th dot comes we can win
ex:
. . . *
. . . *
* * * *
If 7th dot comes then again we will not be able to win in one click. i leave it to you to imagine.
Now, it is very important to understand that for all dots more than 7 we can always form the board such that it is possible to win in one click.
Lets see how
Lets assume we set the board like this for 8 dots
. . . * *
. . . * *
. . * * *
* * * * *
* * * * *
Now we will take next 2 dots and set them together in first two columns of rows like this
. . . * *
. . . * *
. . * * *
. . * * *
. . * * *
at any point of time if we are left with 1 dot, we star making pairs of 3
. . . * *
. . . * *
. . . * *
. . * * *
* * * * *
Lets say there are more dots in pair of 2’s then we fill first two rows like this
. . . . .
. . . . .
. . * * *
. . * * *
. . * * *
Now if we are left with more dots we just arrange them in 3rd row , then 4th row and so on.
. . . . .
. . . . .
. . . . *
. . . . *
. . . * *
We can see that in all of the above formations we can wil by just clicking the very first dot.
Here is the java code for Minesweeper Master Google Code Jam 2014 problem
package codejam2014;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;
public class MinesweeperMaster {
public char[][] getBoard(int R, int C, int M) throws Exception{
char[][] board = new char[R][C];
int left = C*R - M;
if(left == 1){
fillBoardWithChar(board, C, R, '*');
board[0][0] = 'c';
return board;
}
if(C == 1 || R == 1)
{
fillBoardWithChar(board, C, R, '.');
fillBoardForOneRow(C, R, M, board);
return board;
}
if( C == 2 || R == 2){
fillBoardWithChar(board, C, R, '.');
fillBoardForTwoRow(C, R, M, board);
return board;
}
fillBoardWithChar(board, C, R, '*');
fillBoard(C, R, M, board);
return board;
}
private void fillBoard(int C, int R, int M, char[][] board) throws Exception{
int left = C*R - M;
if(left < 4 || left == 5 || left == 7){ throw new Exception("Impossible"); } //first fill the 4 dots in this shape // c . // . . board[0][0] = board[0][1] = board[1][0] = board[1][1] = '.'; left -= 4; if(left > 1)
{
//then fill 2 more dots in x direction
board[0][2] = board[1][2] = '.';
left -= 2;
}
//now fill in y direction in pair of 2
for(int iy = 2; iy < R && left > 1; iy++){
board[iy][0] = board[iy][1] = '.';
left -=2;
}
//Now fill in x direction in pair of 2, second line we had already filled
for(int ix = 3; ix < C && left > 1; ix++){
board[0][ix] = board[1][ix] = '.';
left -=2;
}
//Now we keep on filling dots along y direction one by one
for(int ix = 2; ix < C && left > 0; ix ++){
for(int iy =2; iy < R && left > 0; iy++){
board[iy][ix] = '.';
left--;
}
}
board[0][0] = 'c';
}
private void fillBoardForTwoRow(int C, int R, int M, char[][] board) throws Exception{
int left = C*R - M;
board[0][0] = 'c';
//left =1 case handled befofe calling this function
//if left is from 2 to 3 its not possible
//or if left is not a pair of 2 its not possible
if(left < 4 || left%2 == 1){ throw new Exception("Impossible\n"); } if(C == 2){ for(int i = R-1; i >=0 & M > 0; i--){
board[i][0] = '*';
board[i][1] = '*';
M -= 2;
}
}
if(R == 2){
for(int i = C-1; i >=0 & M > 0; i--){
board[0][i] = '*';
board[1][i] = '*';
M -=2;
}
}
}
private void fillBoardForOneRow(int C, int R, int M, char[][] board){
board[0][0] = 'c';
if(C == 1){
for(int i = R-1; i >=0 & M > 0; i--){
board[i][0] = '*';
M--;
}
}
if(R == 1){
for(int i = C-1; i >=0 & M > 0; i--){
board[0][i] = '*';
M--;
}
}
}
private void fillBoardWithChar(char[][] board, int C, int R, char c){
for(int i=0; i < R; i++){
for(int j=0; j < C; j++){
board[i][j] = c;
}
}
}
private static void printBoard(char[][] board){
for(int i =0; i < board.length; i++){
for(int j=0; j < board[i].length; j++){
System.out.print(board[i][j]);
}
System.out.println();
}
}
private static void printBoardInFile(char[][] board, FileWriter writer) throws IOException{
for(int i =0; i < board.length; i++){
for(int j=0; j < board[i].length; j++){
writer.write(board[i][j]);
}
writer.write("\n");
}
}
public static void main(String[] argv) {
try {
long startTime = System.currentTimeMillis();
Reader reader = new FileReader("small.in");
BufferedReader bufReader = new BufferedReader(reader);
String x = bufReader.readLine();
int numOfTestCases = Integer.parseInt(x);
int count = 0;
File file = new File("small.out");
FileWriter writer = new FileWriter(file);
for(count =1; count<= numOfTestCases; count++) {
ArrayList secondLine = getIntegerList(bufReader.readLine());
writer.write("Case #" + count + ":\n");
System.out.println("Case #" + count + ":");
try{
char[][] board = new MinesweeperMaster().getBoard(secondLine.get(0), secondLine.get(1), secondLine.get(2));
printBoard(board);
printBoardInFile(board, writer);
}catch (Exception e) {
// TODO: handle exception
writer.write("Impossible\n");
System.out.println("Impossible");
}
}
writer.close();
System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
} catch (Exception e) {
e.printStackTrace();
}
}
private static ArrayList getIntegerList(String s) {
ArrayList intList = new ArrayList();
String[] strArr = s.split(" ");
for (String str : strArr) {
intList.add(Integer.parseInt(str.trim()));
}
return intList;
}
}
