Count the number of "holes" in a bitmap

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:

11111  
10101  
10101  
11111  

... and this has only one:

11111  
10001  
10101  
11111

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开发者_如何学Python that takes advantage of the data format. I know how to transform this into a graph and [BD]FS it but that seems overkill.

You need to do connected component labeling on your image. You can use the Two-pass algorithm described in the Wikipedia article I linked above. Given the small size of your problem, the One-pass algorithm may suffice.

You could also use BFS/DFS but I'd recommend the above algorithms.

This seems like a nice use of the disjoint-set data structure.
Convert the bitmap to a 2d array
loop through each element
if the current element is a 0, merge it with the set of one its 'previous' empty neighbors (already visited)
if it has no empty neighbors, add it to its own set

then just count the number of sets

There may be advantages gained by using table lookups and bitwise operations.

For example whole line of 8 pixels may be looked up in 256 element table, so number of holes in a field 1xN is got by single lookup. Then there may be some lookup table of 256xK elements, where K is number of hole configurations in previous line, contatining number of complete holes and next hole configuration. That's just an idea.

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()

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<indexOfZ[i].length ; j++){
          if(indexOfZ[i+1] && (indexOfZ[i][j]==indexOfZ[i+1][j] || indexOfZ[i+1].indexOf(indexOfZ[i][j])))
          returnArry.indexOf(strArr[i]) < 0 ? returnArry.push(strArr[i]): false;
          if(Math.abs(indexOfZ[i][j]-indexOfZ[i][j+1])==1)
          returnArry.indexOf(strArr[i]) < 0 ? returnArry.push(strArr[i]): false;
        }
    }
    
      return returnArry.length; 
    
    }
       
    // keep this function call here 
    console.log(BitmapHoles(readline()));

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;
}