> For the complete documentation index, see [llms.txt](https://soveet-nayak.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soveet-nayak.gitbook.io/algorithms/graph/minesweeper-lite.md).

# Minesweeper Lite

## Replace all occurrences of 0 that are surrounded by 1 in a binary matrix

Given an `M × N` binary matrix, replace all occurrences of 0’s by 1’s, which are completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).

For example, consider the following matrix:

 \[  1  1  1  1  0  0  1  1  0  1  ]\
 \[  1  0  0  1  1  0  1  1  1  1  ]\
 \[  1  0  0  1  1  1  1  1  1  1  ]\
 \[  1  1  1  1  0  0  1  1  0  1  ]\
 \[  0  0  1  1  0  0  0  1  0  1  ]\
 \[  1  0  0  1  1  0  1  1  0  0  ]\
 \[  1  1  0  1  1  1  1  1  1  1  ]\
 \[  1  1  0  1  1  0  0  1  0  1  ]\
 \[  1  1  1  0  1  0  1  0  0  1  ]\
 \[  1  1  1  0  1  1  1  1  1  1  ]

The solution should convert it into the following matrix:

 \[  1  1  1  1  0  0  1  1  0  1  ]\
 \[  1  1  1  1  1  0  1  1  1  1  ]\
 \[  1  1  1  1  1  1  1  1  1  1  ]\
 \[  1  1  1  1  1  1  1  1  0  1  ]\
 \[  0  0  1  1  1  1  1  1  0  1  ]\
 \[  1  0  0  1  1  1  1  1  0  0  ]\
 \[  1  1  0  1  1  1  1  1  1  1  ]\
 \[  1  1  0  1  1  1  1  1  1  1  ]\
 \[  1  1  1  0  1  1  1  1  1  1  ]\
 \[  1  1  1  0  1  1  1  1  1  1  ]

We can use the flood fill algorithm to solve this problem. The idea is to consider all zeroes present on the matrix’s boundary one by one and start a Depth–first search (DFS) from them. The DFS procedure replaces all such connected zeroes by value `-1`.

After processing all connected zeroes present on the matrix boundary, traverse the matrix again, replace all remaining zeroes with `1` and replace all `-1`