我有一个用螺旋算法排序的坐标列表。我需要从该区域的中间开始并“触摸”任何坐标。
为了简化这是(未排序的)坐标列表的表示(x,y 在下图中用“点”标记)。
CSV 坐标列表可在此处获得。
X 从左到右
增加 Y 从 TOP 到 BOTTOM 增加
每个坐标都与下一个坐标不相邻,而是相隔 1 或 2 个骰子(或在某些情况下更多)。
从区域的中心开始,我需要通过螺旋运动来触摸任何坐标:
解析每个坐标我已经起草了这个 PHP 算法:
//$missing is an associative array having as key the coordinate "x,y" to be touched
$direction = 'top';
$distance = 1;
$next = '128,127'; //starting coordinate
$sequence = array(
$next;
)
unset($missing[$next]);
reset($missing);
$loopcount = 0;
while ($missing) {
for ($loop = 1; $loop <= 2; $loop++) {
for ($d = 1; $d <= $distance; $d++) {
list($x,$y) = explode(",", $next);
if ($direction == 'top') $next = ($x) . "," . ($y - 1);
elseif ($direction == 'right') $next = ($x + 1) . "," . ($y);
elseif ($direction == 'bottom') $next = ($x) . "," . ($y + 1);
elseif ($direction == 'left') $next = ($x - 1) . "," . ($y);
if ($missing[$next]) {
unset($missing[$next]); //missing is reduced every time that I pass over a coordinate to be touched
$sequence[] = $next;
}
}
if ($direction == 'top') $direction = 'right';
elseif ($direction == 'right') $direction = 'bottom';
elseif ($direction == 'bottom') $direction = 'left';
elseif ($direction == 'left') $direction = 'top';
}
$distance++;
}
但由于坐标彼此不等距,我得到这个输出:
可以清楚地看到,中间的运动是正确的,而相应的坐标位置,在某个时刻,每个坐标之间的跳跃不再连贯。
我怎样才能修改我的代码以获得这样的方法呢?
为了简化/减少问题:想象上图中显示的点是推销员必须经常访问的城市。从区域中间的“城市”开始,接下来要参观的城市是位于起点附近的城市,位于起点的北、东、苏奇和西。除非没有访问过起点回合中的所有相邻城市,否则推销员不能访问任何其他城市。所有城市都只能参观一次。