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