php扫地机器人算法

佚名 6年前 (2019-04-10) 随笔 524人围观抢沙发百度已收录

优秀的扫地机器人

现在有很多制造商都在卖扫地机器人，它非常有用，能为忙碌的我们分担家务负担。不过我们也很难理解为什么扫地机器人有时候会反复清扫某一个地方。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

假设有一款不会反复清扫同一个地方的机器人，它只能前后左右移动。举个例子，如果第1 次向后移动，那么连续移动3 次时，就会有以下9 种情况（图6 ）。又因为第1 次移动可以是前后左右4 种情况，所以移动3 次时全部路径有9×4 ＝ 36 种。

※ 最初的位置用0 表示，其后的移动位置用数字表示。

 1 <?php
 2 ini_set('memory_limit','1024M');
 3 function check($positions,$next_position){
 4     foreach ($positions as $key => $value) {
 5         if ($value === $next_position) {
 6             return false;
 7         }
 8     }
 9     return true;
10 }
11 
12 /**
13  * 向上 y+1 向下 y-1
14  * 向左 x-1 向右 x+1
15  */
16 $position = ['x'=>0,'y'=>0];
17 
18 
19 $position["y"] -= 1;
20 $positions_0 = [
21     [
22         ['x'=>0,'y'=>0],
23     ]
24 ];
25 $positions = [
26     [
27         ['x'=>0,'y'=>0],
28     ]
29 ];
30 for($i =0;$i<12; $i ++){
31     $tmp = [];
32     foreach ($positions as $key => $value) {
33         $last_position = end($value);
34         $next_position = ['x'=>$last_position['x']-1,'y'=>$last_position['y']];
35         if (check($value,$next_position)) {
36             $tmp[] = array_merge($value,[$next_position]);
37         }
38         $next_position = ['x'=>$last_position['x']+1,'y'=>$last_position['y']];
39         if (check($value,$next_position)) {
40             $tmp[] = array_merge($value,[$next_position]);
41         }
42         $next_position = ['x'=>$last_position['x'],'y'=>$last_position['y']-1];
43         if (check($value,$next_position)) {
44             $tmp[] = array_merge($value,[$next_position]);
45         }
46         $next_position = ['x'=>$last_position['x'],'y'=>$last_position['y']+1];
47         if (check($value,$next_position)) {
48             $tmp[] = array_merge($value,[$next_position]);
49         }
50     }
51     $positions = $tmp;
52 }
53 
54 echo count($positions);