Published on

Minesweeper

Authors

Problem

In the game of Minesweeper, the player is presented with a board which contains some mines and cells that don't have mines. The cells that don't contain a mine have a number in them that represents the total number of mines in the neighboring cells. The goal is to create a Minesweeper game setup, starting with an initial arrangement of mines on the board.

Example

For


_3
matrix = [[true, false, false],
_3
[false, true, false],
_3
[false, false, false]]

the output should be


_3
solution(matrix) = [[1, 2, 1],
_3
[2, 1, 1],
_3
[1, 1, 1]]

Input/Output

[input] array.array.boolean matrix

A non-empty rectangular matrix consisting of boolean values - true if the corresponding cell contains a mine, false otherwise.

Guaranteed constraints: 2 ≤ matrix.length ≤ 100, 2 ≤ matrix[0].length ≤ 100.

[output] array.array.integer

Rectangular matrix of the same size as matrix each cell of which contains an integer equal to the number of mines in the neighboring cells. Two cells are called neighboring if they share at least one corner.

Solution

Solving this problem is very straihtforward.

  1. Walking through all matrix positions.
  2. Check the surrounding cells containing a mine and count all mines in them.
  3. Update current cell with total mines in neighbor, include diagonal neighbor.

Step 1

Define all direction to check the neighbor values.

solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 2

Get max row and column matrix and create helper outOfBounds function to check matrix position outside matrix or not.

solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 3

Create place holder result array.

solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 4

Iterate through all matrix.

solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 5

Find the neighbor with bomb:

  • if neighbor is out of bounds, ignore
  • every a bomb that found in the neighbor, increase 1 value to the current position.
solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 6

Return result array

solution.go

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}

Step 1

Define all direction to check the neighbor values.

Step 2

Get max row and column matrix and create helper outOfBounds function to check matrix position outside matrix or not.

Step 3

Create place holder result array.

Step 4

Iterate through all matrix.

Step 5

Find the neighbor with bomb:

  • if neighbor is out of bounds, ignore
  • every a bomb that found in the neighbor, increase 1 value to the current position.

Step 6

Return result array

solution.go
ExpandClose

_39
func solution(matrix [][]bool) [][]int {
_39
// all directions, including diagonal
_39
allDirections := [][2]int{
_39
{-1, -1}, // diag upper left
_39
{0, -1}, // left
_39
{1, -1}, // diag lower left
_39
{-1, 0}, // up
_39
{1, 0}, // down
_39
{-1, 1}, // diag upper right
_39
{0, 1}, // right
_39
{1, 1}, // diag lower right
_39
}
_39
maxRow, maxCol := len(matrix), len(matrix[0])
_39
_39
// helper func to check bounds of a position in the grid
_39
outOfBounds := func(r, c int) bool {
_39
return r < 0 || r >= maxRow || c >= maxCol || c < 0
_39
}
_39
_39
result:=make([][]int, maxRow)
_39
_39
for row := range matrix{
_39
result[row] = make([]int, maxCol)
_39
for col:= range matrix[row]{
_39
for _, coords := range allDirections {
_39
r,c := coords[0]+row,coords[1]+col
_39
if outOfBounds(r,c) {
_39
continue
_39
}
_39
// if a neighbor is bomb add counter
_39
if matrix[r][c]{
_39
result[row][col]+=1
_39
}
_39
}
_39
}
_39
}
_39
_39
return result
_39
}