セルが0または1であるMxNビットマップについて考えてみます。「1」は塗りつぶされ、「0」は空を意味します。
ビットマップ内の「穴」の数を見つけます。ここで、穴は空のセルの連続した領域です。
たとえば、これには2つの穴があります。
11111
10101
10101
11111
...そしてこれには1つしかありません：
11111
10001
10101
11111
MとNが両方とも1から8の間にある場合、最速の方法は何ですか？
明確化：対角線は隣接しているとは見なされず、隣接関係のみが重要です。
注：データ形式を利用するものを探しています。これをグラフに変換して[BD]FSする方法は知っていますが、それはやり過ぎのようです。
画像に連結成分のラベル付けを行う必要があります。上記でリンクしたウィキペディアの記事で説明されている2パスアルゴリズムを使用できます。問題のサイズが小さいことを考えると、ワンパスアルゴリズムで十分な場合があります。
これは、素集合データ構造の良い使い方のようです。
現在の要素が0の場合、ビットマップを各要素を介して2D配列
ループに変換し、空のネイバーがない場合
は、その「前の」空のネイバー（すでにアクセス済み）のセットとマージし
、独自のセットに追加します
次に、セットの数を数えるだけです
テーブルルックアップとビット演算を使用することで得られる利点があるかもしれません。
たとえば、8ピクセルのライン全体を256要素のテーブルで検索できるため、フィールド1xNの穴の数は1回の検索で取得されます。次に、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()