Minesweeper

The single player game of minesweeper is played on a rectangular grid. Each cell in this grid is either vacant or contains a mine. When the game begins, all cells are covered so the player cannot tell if a cell contains a mine. Plays consist of selecting and uncovering cells, one at a time. If an uncovered cell contains a mine, the game is over. If the cell does not contain a mine, it reveals an integer that indicates the number of neighboring cells that do contain mines. Neighboring cells are those that are immediately adjacent either horizontally, vertically, or diagonally.

 

In this problem, you are given a game grid on which some number of plays has already been made without uncovering a mine. You are to determine the status of those still covered cells whose status can be determined using only the information revealed by the uncovered cells. That is, for each cell still covered, determine if its status can be discovered, and if so, whether or not it contains a mine.

 

As an example, consider the grids shown below. The cells with the darker background color and without a number represent cells that are still covered. The cells containing a number are uncovered, and the number each contains indicates the number of neighboring cells that contain mines. In the left grid, it is clear that the rightmost uncovered cell in the top row contains a mine, as do the last uncovered cell in the leftmost column and the rightmost uncovered cell in the second row from the top. These cells have been marked with an asterisk (*) for clarity. We can now determine that the covered cells marked with a plus sign (+) have no mines. The status of the cell in the upper left corner of the grid cannot be determined. In the right grid, we cannot unambiguously determine the status of any uncovered cells. It could be that the first or second cell in the top row contains a mine, with the other cell not containing a mine.

 

+

+

*

1

+

*

2

1

1

+

2

1

0

0

*

1

0

0

0

1

1

0

0

0

 

 

 

1

1

 

 

Input

The input data will contain multiple cases. Each case begins with integers giving the number of rows and columns in the grid. There will be no more than 10 rows and 10 columns in the grid. Following these there will be one integer for each cell in the grid, given in row major order. For a covered cell, the value –1 is given. For an uncovered cell, the number of neighboring (covered) cells that contain mines is given, a value between 0 and 8. No uncovered cells contain mines. A pair of zeroes follows the data for the last case.

 

Output

For each case, first display the case number. Cases are numbered sequentially, starting with 1. Then display a list with the row and column number of each cell that definitely contains a mine, and another list with the row and column number of each cell that definitely does not contain a mine. The lists are to be displayed in a format similar to that shown in the sample below. Separate the output for consecutive cases with a blank line.

 

Sample Input

5 5

-1 -1 -1 -1  1

-1 -1  2  1  1

-1  2  1  0  0

-1  1  0  0  0

 1  1  0  0  0

 

2 2

-1 -1

 1  1

 

0 0

 

Expected Output

Case 1:

Cells with mines: (1,4), (2,2), (4,1)

Cells without mines: (1,2), (1,3), (2,1), (3,1)

Case 2:

Cells with mines:

Cells without mines:

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s