Count the number of "holes" in a bitmap

Question

Consider a MxN bitmap where the cells are 0 or 1. '1' means filled and '0' means empty.

Find the number of 'holes' in the bitmap, where a hole is a contiguous region of empty cells.

For example, this has two holes:

... and this has only one:

What is the fastest way, when M and N are both between 1 and 8?

Clarification: diagonals are not considered contiguous, only side-adjacency matters.

Note: I am looking for something that takes advantage of the data format. I know how to transform this into a graph and [BD]FS it but that seems overkill.

user_6118166 · Answer

I wrote an article describe the answer on Medium https://medium.com/@ahmed.wael888/bitmap-holes-count-using-typescript-javascript-387b51dd754a

but here is the code, the logic isn't complicated and you can understand it without reading the article.

export class CountBitMapHoles {
    bitMapArr: number[][];
    holesArr: Hole[] = [];
    maxRows: number;
    maxCols: number;

    constructor(bitMapArr: string[] | number[][]) {
        if (typeof bitMapArr[0] == 'string') {
            this.bitMapArr = (bitMapArr as string[]).map(
                (word: string): number[] => word.split('').map((bit: string): number => +bit))
        } else {
            this.bitMapArr = bitMapArr as number[][]
        }
        this.maxRows = this.bitMapArr.length;
        this.maxCols = this.bitMapArr[0].length;
    }

    moveToDirection(direction: Direction, currentPosition: number[]) {
        switch (direction) {
            case Direction.up:
                return [currentPosition[0] - 1, currentPosition[1]]

            case Direction.down:
                return [currentPosition[0] + 1, currentPosition[1]]

            case Direction.right:
                return [currentPosition[0], currentPosition[1] + 1]

            case Direction.left:
                return [currentPosition[0], currentPosition[1] - 1]

        }
    }
    reverseDirection(direction: Direction) {
        switch (direction) {
            case Direction.up:
                return Direction.down;
            case Direction.down:
                return Direction.up
            case Direction.right:
                return Direction.left
            case Direction.left:
                return Direction.right
        }
    }
    findNeighbor(parentDir: Direction, currentPosition: number[]) {
        let directions: Direction[] = []
        if (parentDir === Direction.root) {
            directions = this.returnAvailableDirections(currentPosition);
        } else {
            this.holesArr[this.holesArr.length - 1].positions.push(currentPosition)
            directions = this.returnAvailableDirections(currentPosition).filter((direction) => direction != parentDir);
        }
        directions.forEach((direction) => {
            const childPosition = this.moveToDirection(direction, currentPosition)
            if (this.bitMapArr[childPosition[0]][childPosition[1]] === 0 && !this.checkIfCurrentPositionExist(childPosition)) {
                this.findNeighbor(this.reverseDirection(direction), childPosition)
            }
        });
        return
    }
    returnAvailableDirections(currentPosition: number[]): Direction[] {
        if (currentPosition[0] == 0 && currentPosition[1] == 0) {
            return [Direction.right, Direction.down]
        } else if (currentPosition[0] == 0 && currentPosition[1] == this.maxCols - 1) {
            return [Direction.down, Direction.left]
        } else if (currentPosition[0] == this.maxRows - 1 && currentPosition[1] == this.maxCols - 1) {
            return [Direction.left, Direction.up]
        } else if (currentPosition[0] == this.maxRows - 1 && currentPosition[1] == 0) {
            return [Direction.up, Direction.right]
        } else if (currentPosition[1] == this.maxCols - 1) {
            return [Direction.down, Direction.left, Direction.up]
        } else if (currentPosition[0] == this.maxRows - 1) {
            return [Direction.left, Direction.up, Direction.right]
        } else if (currentPosition[1] == 0) {
            return [Direction.up, Direction.right, Direction.down]
        } else if (currentPosition[0] == 0) {
            return [Direction.right, Direction.down, Direction.left]
        } else {
            return [Direction.right, Direction.down, Direction.left, Direction.up]
        }
    }
    checkIfCurrentPositionExist(currentPosition: number[]): boolean {
        let found = false;
        return this.holesArr.some((hole) => {
            const foundPosition = hole.positions.find(
                (position) => (position[0] == currentPosition[0] && position[1] == currentPosition[1]));
            if (foundPosition) {
                found = true;
            }
            return found;
        })

    }

    exec() {
        this.bitMapArr.forEach((row, rowIndex) => {
            row.forEach((bit, colIndex) => {
                if (bit === 0) {
                    const currentPosition = [rowIndex, colIndex];
                    if (!this.checkIfCurrentPositionExist(currentPosition)) {
                        this.holesArr.push({
                            holeNumber: this.holesArr.length + 1,
                            positions: [currentPosition]
                        });
                        this.findNeighbor(Direction.root, currentPosition);
                    }
                }
            });
        });
        console.log(this.holesArr.length)
        this.holesArr.forEach(hole => {
            console.log(hole.positions)
        });
        return this.holesArr.length
    }
}
enum Direction {
    up = 'up',
    down = 'down',
    right = 'right',
    left = 'left',
    root = 'root'
}

interface Hole {
    holeNumber: number;
    positions: number[][]
}

main.ts file

import {CountBitMapHoles} from './bitmap-holes'

const line = ['1010111', '1001011', '0001101', '1111001', '0101011']
function main() {
    const countBitMapHoles = new CountBitMapHoles(line)
    countBitMapHoles.exec()
}

main()

user_6345202 · Answer


function BitmapHoles(strArr) { 
    let returnArry = [];
    let indexOfZ = [];
    let subarr;
     for(let i=0 ; i < strArr.length; i++){
       subarr = strArr[i].split("");
      let index = [];
      for(let y=0 ; y < subarr.length; y++){
        if(subarr[y] == 0)
        index.push(y);
        if(y == subarr.length-1)
        indexOfZ.push(index);
      }
    }
    for(let i=0 ; i < indexOfZ.length; i++){
        for(let j=0; j

user_13456061 · Answer

function findHoles(map) {
    let hole = 0;

    const isHole = (i, j) => map[i] && map[i][j] === 0;

    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map[i].length; j++) {
            if (isHole(i, j)) {
                markHole(i, j);
                hole++;
            }
        }
    }

    function markHole(i, j) {
        if (isHole(i, j)) {
            map[i][j] = 2;
            markHole(i, j - 1);
            markHole(i, j + 1);
            markHole(i + 1, j);
            markHole(i - 1, j);
        }
    }

    return hole;
}

Count the number of "holes" in a bitmap

6 Answers