📔
Algorithms Analysis & Design
  • Algorithm Analysis & Design
  • 🚢Searching and Sorting
    • Introduction-Search
    • Linear Search
    • Binary Search
    • Interpolation Search
    • Introduction-Sorting
    • Bubble Sort
    • Selection Sort
    • Counting Sort
  • 💸Greedy Method
    • Introduction
    • Activity Selection
    • Fractional Knapsack Problem
    • Graph Colouring
  • 🚠Backtracking
    • Introduction
    • Hamiltonian Path/Cycle Problem
    • N Queen Problem
    • Rat in a Maze
    • Knight's Tour Problem
  • ⚔️Divide and Conquer
    • Introduction
    • Strassen's Matrix multiplication
    • Karatsuba algorithm
    • Tower of Hanoi
    • Closest Pair
  • 💣Dynamic Programming
    • Introduction
    • Longest Common Subsequence
    • Floyd-Warshall Algorithm
    • 0-1 Knapsack problem
    • Dice Throw
  • 📈Graph
    • Introduction
    • DFS
    • Dictionary Game
    • BFS
    • Flood Fill Algorithm
    • Minesweeper Lite
  • 🔢Number Theory
    • Introduction
    • GCD
    • Factorial
    • IsPrime | School Method
    • IsPrime | Fermat's Little Theorem
    • IsPrime | Miller-Rabin Method
  • 🌮References
Powered by GitBook
On this page

Was this helpful?

  1. Graph

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

PreviousFlood Fill AlgorithmNextIntroduction

Last updated 3 years ago

📈