考虑一个 MxN 位图，其中单元格为 0 或 1。“1”表示填充，“0”表示空。
查找位图中“孔”的数量，其中孔是空单元的连续区域。
例如，这有两个孔：
11111
10101
10101
11111
...而这只有一个：
11111
10001
10101
11111
当 M 和 N 都在 1 和 8 之间时，最快的方法是什么？
澄清：对角线不被认为是连续的，只有边相邻很重要。
注意：我正在寻找利用数据格式的东西。我知道如何将其转换为图表并 [BD] FS ，但这似乎有点过头了。
这似乎是对不相交集数据结构的一个很好的使用。
如果当前元素为 0，则将位图转换为
遍历每个元素的 2d 数组，如果没有空邻居，则将
其与“先前”空邻居（已访问）的集合合并，将其
添加到自己的集合中
然后只计算套数
使用表查找和按位运算可能会带来一些好处。
例如，可以在 256 元素表中查找 8 像素的整行，因此通过单次查找获得字段 1xN 中的孔数。然后可能有一些 256xK 元素的查找表，其中 K 是上一行中的孔配置数，包含完整孔数和下一个孔配置。这只是一个想法。
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()));
我写了一篇文章描述了 Medium https://medium.com/@ahmed.wael888/bitmap-holes-count-using-typescript-javascript-387b51dd754a上的答案
但是这里是代码，逻辑并不复杂，不看文章也能看懂。
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 文件
import {CountBitMapHoles} from './bitmap-holes'
const line = ['1010111', '1001011', '0001101', '1111001', '0101011']
function main() {
const countBitMapHoles = new CountBitMapHoles(line)
countBitMapHoles.exec()
}
main()