不过黑点连线的程序解法
大家都见过下题吧,本人试图连过几次,发现不可能,猜测是无解的,最终写程序穷举,发现是无解的。当然根据图论,奇点跟偶点相差为2是不可能连接上的(再讨论),现列出我的PHP程序穷举法,用到了循环
操作方法
- 01
php文件代码如下: <?php $nodes = array( array(0, 1, 2, 3, 4), array(10,11,12,13,14), array(20,21,22,23,24), array(30,31,32,33,34), array(40,41,42,43,44), ); function nextNodes($node) { $next_nodes = array(); $next_nodes[] = $node + 10; $next_nodes[] = $node - 10; $next_nodes[] = $node + 1; $next_nodes[] = $node - 1; foreach($next_nodes as $key => $next_node){ if( $next_node<0 || $next_node>44 || $next_node==1 || $next_node%10>4) { unset($next_nodes[$key]); } } return $next_nodes; } $nextNodes = array(); //得到所有的次节点 foreach ($nodes as $rownum => $cols){ foreach($cols as $colnum => $node){ $nextNodes[$rownum][$colnum] = nextNodes($node); } } unset($nextNodes[0][1]); function connect($routes){ global $nextNodes; $new_routes = array(); $i = 0; foreach ($routes as $route){ $current = end($route); $next_nodes = $nextNodes[floor($current/10)][floor($current%10)]; foreach($next_nodes as $key => $node){ if(!in_array($node, $route)){ $new_routes[$i] = $route; $new_routes[$i][] = $node; $i++; } } } return $new_routes; } $node = 0; foreach($nodes as $rownum => $rows) { foreach($rows as $colnum => $node){ //echo "\n\n"; if($node == 1) continue; $times = 2; $routes = array(array($node)); while($times < 25){ $routes = connect($routes); if(!empty($routes)){ //echo "起始点为{$node}的{$times}个连接点的线有".count($routes)."种:\n"; foreach($routes as $key => $route){ // echo implode($route, '--')."\n"; } $times++; } else { echo "起始点为{$node}的{$times}个连接点的线没有\n"; break; } } } }
- 02
执行此文件(如果想看详细的内容,可将部分反注释)
- 03
运行结果: [root@dev sf_codes]# php lianlian.php 起始点为0的24个连接点的线没有 起始点为2的24个连接点的线没有 起始点为3的23个连接点的线没有 起始点为4的24个连接点的线没有 起始点为10的23个连接点的线没有 起始点为11的24个连接点的线没有 起始点为12的23个连接点的线没有 起始点为13的24个连接点的线没有 起始点为14的23个连接点的线没有 起始点为20的24个连接点的线没有 起始点为21的23个连接点的线没有 起始点为22的24个连接点的线没有 起始点为23的23个连接点的线没有 起始点为24的24个连接点的线没有 起始点为30的23个连接点的线没有 起始点为31的24个连接点的线没有 起始点为32的23个连接点的线没有 起始点为33的24个连接点的线没有 起始点为34的23个连接点的线没有 起始点为40的24个连接点的线没有 起始点为41的23个连接点的线没有 起始点为42的24个连接点的线没有 起始点为43的23个连接点的线没有 起始点为44的24个连接点的线没有