[Algo]Cases voisines

[nicodd]

J'ai codé rapidement une solution pour expliciter un peu mon algorithme :

Ca fait quelques mois que je n'ai plus fait de php, donc il se peut que j'aille un peu perdu la main et que ce ne soit pas très optimisé mais cela fonctionne :

<?php

function detectGroups($map, $x, $y, $visited=null)

{

	if($map[$x][$y]==0)

		return false;

	$color=$map[$x][$y];

	if($visited===null)

	{

		$visited=$map;

		foreach($visited as $line)

			foreach($line as $cell)

				$cell=false;

	}

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

	return status($map, $x-1, $y, $color, $visited)

		  && status($map, $x+1, $y, $color, $visited)

		  && status($map, $x, $y-1, $color, $visited)

		  && status($map, $x, $y+1, $color, $visited);

}

function status($map, $x, $y, $color,$visited)

{

	if($x<0 || $x>=count($map) || $y<0 || $y>=count($map[0]))

		return true;

	if($map[$x][$y]==0)

		return false;

	if($map[$x][$y]==$color)

		if(!$visited[$x][$y])

			return detectGroups($map, $x, $y, $visited);

		else

			return true;

	if($map[$x][$y]!=$color)

		return true;

}

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

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

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

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



for($i=0; $i<count($map); $i++)

	for($j=0; $j<count($map[0]); $j++)

		echo "(".$i.",".$j.") : ".detectGroups($map,$i,$j).'<br/>';

?>

Pour le moment la fonction renvoie true lorsque les cases appartenant à un groupe.
Il est assez facile de modifier ça pour que cela puisse renvoyer les coordonnées de tous les groupes présents dans la carte.
N'hésite pas si tu as des questions pour comprendre ou améliorer mon code, et n'hésite pas à tester sur des maps un peu plus compliquées (h)