Gefunden mit folgendem PHP-Programm (Liebe Kinder, macht das bitte so nicht nach
Code: Alles auswählen
<?php
function flood_fill($x,$y,$val) {
global $visited, $width, $height;
for ($i=0; $i<$width; $i++) {
for ($j=0; $j<$height; $j++) {
$visited[$i][$j] = 0;
}
}
return flood_fill_rek($x,$y,$val);
}
function flood_fill_rek($x,$y,$val) {
global $field, $visited;
if ($field[$x][$y] === $val && $visited[$x][$y] === 0) {
$visited[$x][$y] = 1;
return 1 + flood_fill_rek($x-1,$y,$val) + flood_fill_rek($x+1,$y,$val) + flood_fill_rek($x,$y-1,$val) + flood_fill_rek($x,$y+1,$val);
}
else {
return 0;
}
}
function next_step($state,$x,$y,$lastdir,$depth,$val) {
global $best, $width, $height, $deltas, $field, $transitions;
if ($depth>$best) {
return false;
}
if ($state==='u' && ($depth!==$width*$height-1 || $x!==$height-1 || $y!==0)) {
return false;
}
if ($field[$x][$y]!==0) {
return false;
}
$field[$x][$y] = $depth;
if ($depth===$width*$height-1 && $state==='u' && $x===$width-1 && $y===0) {
$best = $val;
echo "$width x $height : $val\n";
for($j = $height -1 ; $j >= 0; $j--) {
for($i = 0; $i < $width; $i++) {
if ($field[$i][$j] < 10 && $field[$i][$j] > -1) echo " ";
echo $field[$i][$j] . ' ';
}
echo "\n";
}
echo "\n";
}
if (flood_fill($width-1,0,0)===$width*$height-1-$depth) {
foreach($deltas[$lastdir] as $direction => $delta) {
$more = ($direction === $lastdir)?0:1;
next_step(
$transitions[$state][$direction],
$x + $delta[0],
$y + $delta[1],
$direction,
$depth + 1,
$val + $more
);
}
}
$field[$x][$y] = 0;
}
$best = 999;
$width = intval($argv[1])?intval($argv[1]):8;
$height = intval($argv[2])?intval($argv[2]):8;
$deltas = array(
'right' => array(
'right' => array(1,0),
'up' => array(0,1),
'down' => array(0,-1)
),
'left' => array(
'left' => array(-1,0),
'up' => array(0,1),
'down' => array(0,-1)
),
'up' => array(
'up' => array(0,1),
'right' => array(1,0),
'left' => array(-1,0)
),
'down' => array(
'down' => array(0,-1),
'right' => array(1,0),
'left' => array(-1,0)
)
);
$transitions = array(
'u' => array('right' => 'r', 'left' => 'l', 'up' => 'b', 'down' => 'f'),
'd' => array('right' => 'l', 'left' => 'r', 'up' => 'f', 'down' => 'b'),
'l' => array('right' => 'u', 'left' => 'd', 'up' => 'l', 'down' => 'l'),
'r' => array('right' => 'd', 'left' => 'u', 'up' => 'r', 'down' => 'r'),
'f' => array('right' => 'f', 'left' => 'f', 'up' => 'u', 'down' => 'd'),
'b' => array('right' => 'b', 'left' => 'b', 'up' => 'd', 'down' => 'u')
);
$field = array();
for ($i=0; $i<$width; $i++) {
for ($j=0; $j<$height; $j++) {
$field[$i][$j] = 0;
$field[-1][$j] = -1;
$field[$width][$j] = -1;
$field[$i][-1] = -1;
$field[$i][$height] = -1;
}
}
$visited = $field;
$field[0][0] = -1;
next_step('r',1,0,'right',1,0);
next_step('b',0,1,'up',1,0);
?>
Der Trick ist nach jedem Schritt auf Zusammenhang aller Restfelder zu testen, da kann viel Backtracking vermieden werden.
