Skip to content

Instantly share code, notes, and snippets.

@oceangravity
Created December 2, 2021 11:56
Show Gist options
  • Save oceangravity/8edbe738fe820e29f8e79079a962da7f to your computer and use it in GitHub Desktop.
Save oceangravity/8edbe738fe820e29f8e79079a962da7f to your computer and use it in GitHub Desktop.
Bitmap Holes
<?php
/**
* Bitmap Holes
* Have the function BitmapHoles(strArr) take the array of strings stored in strArr,
* which will be a 2D matrix of 0 and 1's, and determine how many holes, or contiguous regions of 0's,
* exist in the matrix. A contiguous region is one where there is a connected group of 0's going
* in one or more of four directions: up, down, left, or right.
*
* For example: if strArr is ["10111", "10101", "11101", "11111"], then this looks like the following matrix:
*
* 1 0 1 1 1
* 1 0 1 0 1
* 1 1 1 0 1
* 1 1 1 1 1
*
* For the input above, your program should return 2 because there are two separate contiguous regions of 0's, which create "holes" in the matrix. You can assume the input will not be empty.
*/
function checkHole($row, $column, $array)
{
// previous
if ($column >= 1 && $array[$row][$column - 1] == '0') {
$array[$row][$column - 1] = 'H';
$array = checkHole($row, $column - 1, $array);
}
// next
if (isset($array[$row][$column + 1]) && $array[$row][$column + 1] == '0') {
$array[$row][$column + 1] = 'H';
$array = checkHole($row, $column + 1, $array);
}
// up
if ($row - 1 >= 0 && $array[$row - 1][$column] == '0') {
$array[$row - 1][$column] = 'H';
$array = checkHole($row - 1, $column, $array);
}
// down
if ($row + 1 <= (count($array) - 1) && $array[$row + 1][$column] == '0') {
$array[$row + 1][$column] = 'H';
$array = checkHole($row + 1, $column, $array);
}
return $array;
}
function SearchingChallenge($strArr)
{
$holeCount = 0;
$zerosRemain = true;
while ($zerosRemain) {
// we need to traverse
foreach ($strArr as $key => $val) {
// flag to indentify if a zero was found
$foundZero = false;
// now we need to walk each digit
foreach (str_split($val) as $stringKey => $stringVal) {
// check for 0 and mark it!
if ($strArr[$key][$stringKey] == '0') {
// mark it as (H)ole!
$strArr[$key][$stringKey] = 'H';
// now we need to check other sides: up, down, left, right!!!
$strArr = checkHole($key, $stringKey, $strArr);
$foundZero = true;
$holeCount++;
}
if ($stringVal == '1' && $foundZero) {
break;
}
}
$zerosRemain = false;
foreach ($strArr as $key => $val) {
if (str_contains($val, '0')) {
$zerosRemain = true;
break;
}
}
}
}
// code goes here
return $holeCount;
}
// keep this function call here
echo SearchingChallenge(fgets(fopen('php://stdin', 'r')));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment