矩阵中的连通区域

Question

i have a task and i am not sure how i should solve the problem. I have an idead but i do not know if it is the best way to solve it. Here is the task: Given is a 2 dimensional matrix of "1" and "0". Find the exact amount of connected Areas. A connected area consists of "1" that are neighbors of other "1"'s (horizontal, vertical or diagonal does count!). if a "1" is surrounded by "0" this "1" is also a connected area itself. Here are 4 Examples:

Matrix:
0 0 1 0
1 0 1 0
0 1 0 0
1 1 1 1

Solution: 1 (We can connect all 1 together)

1 0 0 1
0 0 0 0
0 1 1 0
1 0 0 1

Solution 3 (both 1 at the first line count as one zone and the other 1's can be connected)

1 0 0 1 1
0 0 1 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

Solution: 3 (one zone at the top left, one zone the 1's top right and the third zone is the 4th column)

0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0

Solution: 9

My idea was to put the numbers into a 2-dimensional array and use it as a coordinate system. i would search for the first "1", set it to 0 and then look around it's position for other "1" (x +/- 1; y +/- 1). if there is another 1 i would replace it with a 0 and search around this one and so on. if there is no "1" around, i would know that i found a complete area. after that i would go through the array and do the same until i have only 0 in my array and the amount of connected areas.

do you think this is the best approach or can you point me to a better idea how i can solve this problem?

Answer 1

this is my solution. $_POST['input'] is an example for the post data from html formular. This solution was my best idea. Do you have another idea?

$_POST['input'] =' 
    4
    4
    0 0 1 0
    1 0 1 0
    0 1 0 0
    1 1 1 1
    4
    1 0 0 1
    0 0 0 0
    0 1 1 0
    1 0 0 1
    5
    1 0 0 1 1
    0 0 1 0 0
    0 0 0 0 0
    1 1 1 1 1
    0 0 0 0 0
    8
    0 0 1 0 0 1 0 0
    1 0 0 0 0 0 0 1
    0 0 1 0 0 1 0 1
    0 1 0 0 0 1 0 0
    1 0 0 0 0 0 0 0
    0 0 1 1 0 1 1 0
    1 0 1 1 0 1 1 0
    0 0 0 0 0 0 0 0
';

if (isset($_POST['input'])) {

    $allMatrizes = convertToArray($_POST['input']);

    foreach ($allMatrizes as $matrix) {
        $matrixSize = count($matrix);
        $amountOfConnectedAreas = searchConnectedAreas($matrix, $matrixSize);
        echo $amountOfConnectedAreas . '<br/>';
    }
}


function convertToArray($input) {
    $input = preg_replace('/[^0-9]/', '', $input);
    $index = 1;
    $count = strlen($input);
    $allMatrizes = [];
    while ($index < $count) {
        $matrixSize = $input[$index];
        $matrix = [];
        $line = [];
        for ($i = 0; $i < $matrixSize * $matrixSize; $i++) {
            if ($i % $matrixSize == 0 && $i != 0) {
                array_push($matrix, $line);
                $line = [];
                array_push($line, $input[$i + $index + 1]);
            } else {
                array_push($line, $input[$i + $index + 1]);
            }
        }
        array_push($matrix, $line);
        $index += $i + 1;
        array_push($allMatrizes, $matrix);
    }
    return $allMatrizes;
}

function searchConnectedAreas($matrix, $matrixSize) {
    $x = 0;
    $y = 0;
    // find the first "1"
    $found = false;
    $connectedAreas = 0;
    while ($y < $matrixSize && $x < $matrixSize) {
        $element = $matrix[$y][$x];
        if ($element == 1) {
            $connectedAreas += 1;
            $matrix = eliminateConnectedArea($matrix, $matrixSize, $x, $y);
        }

        // go on and search for next 1
        $x += 1;
        if ($x == $matrixSize) {
            $x = 0;
            $y  += 1;
        }
    }
    return $connectedAreas;
}

function eliminateConnectedArea($matrix, $matrixSize, $x, $y) {
    // set element to 0
    $matrix[$y][$x] = '0';
    // search around for other 1 and call self
    $newX = $x - 1;
    $newY = $y -1;
    while ($newX <= $x +1 && $newY < $matrixSize && $newY <= $y +1) {
        if ($newX >= 0 && $newY >= 0) {
            $element = $matrix[$newY][$newX];
            if ($element == 1) {
                $matrix = eliminateConnectedArea($matrix, $matrixSize, $newX, $newY);
            }
        }

        $newX += 1;
        if ($newX == $matrixSize || $newX > $x +1) {
            $newX = $x - 1;
            $newY  += 1;
        }
    }
    return $matrix;
}