[Algo]Cases voisines

[niahoo]

Voilà une implémentation possible.
Bien que PHP ne soit pas forcément optimisé pour fonctionner avec de la récursion...

mais ça marche.

Un dernier truc,

quand tu écris $map[0]=array(0,1,0,1,1,1,1,0);
ici le premier 0 symbolise les Y et non pas les X, qui sont représentés par l'odre dans l'array à droite du signe '='.
$map[Y][X] <- le Y sont bien les lignes, lex X les colonnes.

<?php

/* implémentation du test d'encerclement 

Cette implémentation considère qu'un groupe enfermé contre

un bord est enfermé,  et considère  donc que le bord de la

map « joue » pour la couleur adverse

*/







$map=array();

$map[]=array(0,1,0,1,1,1,1,0);

$map[]=array(1,2,1,2,2,1,2,1);

$map[]=array(1,2,1,1,2,1,2,1);

$map[]=array(0,1,1,2,2,1,2,1);

$map[]=array(0,2,2,1,1,1,2,1);

$map[]=array(0,0,0,0,0,1,2,1);

define('white', 1);

define('black', 2);

define('void',  0);

define('circled', 0);





function main_loop($map, $color) {



  $visited = array();

  $groups  = array();

  list($mapx, $mapy) = get_map_size($map);

  for($x = 0; $x < $mapx; $x++) {

    for($y = 0; $y < $mapy; $y++) {

      if(!is_visited($visited,array($x, $y)) && $map[$y][$x] == $color) {

	$node_expand = expand_node($map, $x, $y, $color, $visited, array(),0);

	list($is_circled, $stack, $visited) = $node_expand;

	if($is_circled == circled) {

	  array_push($groups, $stack);

	}

      }

    }

  }

  return $groups;

}



function get_map_size($map) {

  return array(count($map[0]), count($map));

}



/** la fonction expand_node n'est appellée par autre chose qu'elle même qu'avec les coordonnées

    d'une cellule de la couleur choisie **/

function expand_node($map, $x, $y, $color, $visited, $stack, $circle_iter) {

  $visited[$x][$y] = true; 

  $stack[] = array($x, $y);

  $calls = array('top','left','right','bottom');

  foreach($calls as $fun) {

    $side_cell = call_user_func($fun, $x, $y);

    if(cell_exists($map,$side_cell) && !is_visited($visited, $side_cell)) {

      if(cell_color($map, $side_cell) == $color) {

	$node_expand = expand_node($map, $side_cell[0], $side_cell[1], $color, $visited, $stack, $circle_iter);

	list($is_circled, $stack, $visited) = $node_expand;

	$circle_iter += $is_circled;

      }

      elseif(cell_color($map, $side_cell) == void) {

	$circle_iter++;

      }

    }

    /* // Partie à décommenter pour que le bord de la map ne  participe pas à l'encerclement des cases

    elseif(!cell_exists($map, $side_cell)) {

      	$circle_iter++;

    }

    //*/

  }

  return array($circle_iter, $stack, $visited);

}



function cell_color($map, $cell) {

  return $map[$cell[1]][$cell[0]];

}



function top($x, $y) { return array($x, $y-1); }

function left($x, $y) { return array($x-1, $y); }

function right($x, $y) { return array($x+1, $y); }

function bottom($x, $y) { return array($x, $y+1); }



function is_visited($visited, $cell) {

  return isset($visited[$cell[0]][$cell[1]]);

}



function cell_exists($map, $cell) {

  return isset($map[$cell[1]][$cell[0]]);

}



function display_results($groups) {

  echo "Voici les groupes encerclés:\n";

  foreach($groups as $group) {

    echo 'groupe: ';

    foreach($group as $cell)

      echo '('.implode(',', $cell).')';

    echo "\n";

  }

}

display_results(main_loop($map, black));

edit:
une petite optimisation,
remplacer
$calls = array('top','left','right','bottom');
par
$calls = array('right','bottom','top','left');

Puisque on commence en haut à gauche de la map, les groupes seront peut-être plus souvent étendus vers la droite et vers le bas.