Выполните итерацию по 2d массиву логических значений и оставьте только самый большой смежный 2D-объект из двоичных объектов.
Итак, вопрос несколько неловко сформулирован, но я надеюсь, что это прояснит ситуацию.
У меня есть этот образец 2d массив.
$array = array(
array(1, 0, 0, 0, 1, 0, 0, 1),
array(0, 0, 1, 1, 1, 1, 0, 1),
array(0, 1, 1, 0, 1, 0, 0, 0),
array(0, 1, 1, 0, 0, 0, 1, 0),
array(1, 0, 0, 0, 1, 1, 1, 1),
array(0, 1, 1, 0, 1, 0, 1, 0),
array(0, 0, 0, 0, 0, 0, 0, 1)
);
Когда повторяется по строкам (и заканчивается каждой строкой с \ n), и для каждой строки, затем повторяется по столбцу, это будет отображать что-то вроде этого: (░░ = 0, ▓▓ = 1)
▓▓░░░░░░▓▓░░░░▓▓
░░░░▓▓▓▓▓▓▓▓░░▓▓
░░▓▓▓▓░░▓▓░░░░░░
░░▓▓▓▓░░░░░░▓▓░░
▓▓░░░░░░▓▓▓▓▓▓▓▓
░░▓▓▓▓░░▓▓░░▓▓░░
░░░░░░░░░░░░░░▓▓
Но то, что я хотел бы сделать, это «проанализировать» массив и оставить только одну смежную фигуру (ту, у которой больше всего «ячеек»), в этом примере результат будет:
░░░░░░░░▓▓░░░░░░
░░░░▓▓▓▓▓▓▓▓░░░░
░░▓▓▓▓░░▓▓░░░░░░
░░▓▓▓▓░░░░░░░░░░
▓▓░░░░░░░░░░░░░░
░░▓▓▓▓░░░░░░░░░░
░░░░░░░░░░░░░░░░
Мой первоначальный подход состоял в том, чтобы:
-
Присвойте каждой ▓▓ ячейке уникальный номер (будь то абсолютно случайный или текущий номер итерации):
01 02 03 04050607 08 0910 11 1213 14 15 16171819 2021 22 23 24 -
Итерация по массиву МНОГИЕ раз: каждая итерация, каждая ячейка принимает наибольшее уникальное число среди своих соседей. Цикл будет продолжаться бесконечно, пока не будет обнаружено никаких изменений между текущим состоянием и предыдущим состоянием. После последней итерации результат будет следующим:
01 21 08 21212121 08 2121 21 2121 24 21 24242424 2121 24 24 24Теперь все сводится к подсчету значения, которое встречается чаще всего. Затем, повторяя еще раз, чтобы повернуть все ячейки, значение которых не является самой популярной, в 0, получая желаемый результат.
Тем не менее, я чувствую, что это довольно обходной и вычислительно сложный подход для такой простой задачи, и должен быть лучший путь. Любые идеи будут с благодарностью, ура!
Бонусные точки: разделите все капли на массив двумерных массивов, упорядоченных по количеству ячеек, чтобы мы могли сделать что-то и с самым маленьким шариком, тоже
Решение
Всегда весело, эти проблемы. И сделано раньше, поэтому я дам свой код здесь, может быть, вы можете использовать некоторые из них. Это в основном следует за каждой формой, глядя на ячейку и окружающие ее 8 ячеек, и, если они соединяются, переходят в соединительную ячейку, смотрят снова и так далее …
<?php
$shape_nr=1;
$ln_max=count($array);
$cl_max=count($array[0]);
$done=[];
//LOOP ALL CELLS, GIVE 1's unique number
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;
$array[$ln][$cl] = ++$shape_nr;
}}
//DETECT SHAPES
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;
$shape_nr=$array[$ln][$cl];
if(in_array($shape_nr,$done))continue;
look_around($ln,$cl,$ln_max,$cl_max,$shape_nr,$array);
//SET SHAPE_NR to DONE, no need to look at that number again
$done[]=$shape_nr;
}}
//LOOP THE ARRAY and COUNT SHAPENUMBERS
$res=array();
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;
if(!isset($res[$array[$ln][$cl]]))$res[$array[$ln][$cl]]=1;
else $res[$array[$ln][$cl]]++;
}}
//get largest shape
$max = max($res);
$shape_value_max = array_search ($max, $res);
//get smallest shape
$min = min($res);
$shape_value_min = array_search ($min, $res);
// recursive function: detect connecting cells
function look_around($ln,$cl,$ln_max,$cl_max,$nr,&$array){
//create mini array
$mini=mini($ln,$cl,$ln_max,$cl_max);
if($mini===false)return false;
//loop surrounding cells
foreach($mini as $v){
if($array[$v[0]][$v[1]]===0){continue;}
if($array[$v[0]][$v[1]]!==$nr){
// set shape_nr of connecting cell
$array[$v[0]][$v[1]]=$nr;
// follow the shape
look_around($v[0],$v[1],$ln_max,$cl_max,$nr,$array);
}
}
return $nr;
}
// CREATE ARRAY WITH THE 9 SURROUNDING CELLS
function mini($ln,$cl,$ln_max,$cl_max){
$look=[];
$mini=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
foreach($mini as $v){
if( $ln + $v[0] >= 0 &&
$ln + $v[0] < $ln_max &&
$cl + $v[1] >= 0 &&
$cl + $v[1] < $cl_max
){
$look[]=[$ln + $v[0], $cl + $v[1]];
}
}
if(count($look)===0){return false;}
return $look;
}
Другие решения
Я могу думать только о нескольких незначительных улучшениях:
-
Держите связанный список не пустых полей. На шаге 2 вам не нужно трогать n² matrix-elements, вам нужно только касаться тех, что в вашем связанном списке. Который может быть намного меньше в зависимости от того, насколько редка ваша матрица.
-
Вам нужно только сравнить направо, вправо-вниз, влево-вниз и вниз. В противном случае другие направления уже проверены из прежней строки / столбца. Что я имею в виду: когда я больше своего правого соседа, я уже могу изменить номер правого соседа. (то же самое для вниз и вправо). Это вдвое меньше сравнений.
Если размер вашего массива не велик и память не будет проблемой, возможно, рекурсивное решение будет быстрее. Я нашел алгоритм C ++, который делает это здесь:
https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/