PHP 解迷宫之 G + H 最小 可刷新运行 刷新

v1版还有待优化。A*搜索算法。保证了走n步时 G + H ,是最小的。会有误差。实验了几次发现,当点比较密集时n在3-5左右,误差较小。点比较分散时,n>=7,误差较小,n越大,进行的运算越慢。 F = G + H,G = 从起点 A 移动到指定方格的移动代价,H = 从指定的方格移动到终点 的估算成本。

代码:

<?php

$n=30;

$positions=[];
for ($i=0;$i<=$n;$i++){
    for ($j=0;$j<=$n;$j++){
        $positions[] =[$j,$i] ;
    }
}

//开始的点
$startDot=[0,0];
//已经放置的点
$placedDot=[];
//不可放置的点
$notPlacedDot=notPlacedDot($positions,$n);
$placedDot[]=$startDot;



//所有穿过的点
list($lineDot,$finishDot)=line($positions,$startDot,$placedDot,$notPlacedDot,$n);


//平面上的所有迷宫点
$mazePositions=mazePosition($positions,$lineDot);


$line=[];//最终结果
$canReOpen=[];//库存
$startDot=[0,0];//开始的点
$line[]=[0,0];
$count=1;//默认值达到 $stepCount重置
$nextStep=[];//保存改点走$stepCount步有多少种可能
$extraNotPlaceDot=[];//不可放置的点
$stepCount=3;//每次前进几步进行比较
$shortLine=getShortLine($line,$canReOpen,$startDot,$mazePositions,$notPlacedDot,$finishDot,$n,$count,$nextStep,$extraNotPlaceDot,$stepCount);

echo "解迷宫";
echo getHtml($positions,$lineDot,$shortLine,$n);
echo "<br>";
echo "迷宫路线";
echo getAllHtml($positions,$lineDot,$n);
//echo getHtml($positions,$lineDot,$n);


/**
 * 生成迷宫路线
 * @param $positions
 * @param $startDot
 * @param $placedDot
 * @param $notPlacedDot
 * @param $n
 * @return array
 */
function line($positions,$startDot,$placedDot,$notPlacedDot,$n){
    
    $dotWrapper=GetDotWrappers($startDot);
    $key=rand(0,3);
    $nextDot =  $dotWrapper[$key];

    $i=0;
    $notPlacedDotAll =array_merge($notPlacedDot,[]);
    while (in_array($nextDot,$placedDot)||in_array($nextDot,$notPlacedDotAll)){

        $i++;
       if(badDot($nextDot,$placedDot,$notPlacedDot,$n)){//是否是坏点

           $notPlacedDotAll[]=$nextDot;

          $startDot=$placedDot[count($placedDot)-1];
           $dotWrapper=GetDotWrappers($startDot);
           $key=rand(0,3);
           $nextDot =  $dotWrapper[$key];

          if(badDot($startDot,$placedDot,$notPlacedDotAll,$n)){//本身是否是坏点
              $notPlacedDotAll[]= array_pop($placedDot);

              $startDot=$placedDot[count($placedDot)-1];
              $dotWrapper=GetDotWrappers($startDot);
              $key=rand(0,3);
              $nextDot =  $dotWrapper[$key];

          }

        }else{
            $key=rand(0,3);
            $nextDot =  $dotWrapper[$key];

        }
        if($i>4&&count($placedDot)>1){//循环大于3次 还没找到去除该点
            $i=0;
            $notPlacedDot[]= array_pop($placedDot);
            $startDot=$placedDot[count($placedDot)-1];
            $dotWrapper=GetDotWrappers($startDot);
            $key=rand(0,3);
            $nextDot =  $dotWrapper[$key];


        }

    }


    $placedDot[]=$nextDot;

   if($nextDot[0]>=$n&&$nextDot[1]>0&&$nextDot[1]<=$n){
       return [$placedDot,$nextDot];
   }
   return line($positions,$nextDot,$placedDot,$notPlacedDot,$n);
}

/**
 * 所有迷宫的点
 * @param $positions
 * @param $lineDot
 * @return array
 */
function mazePosition($positions,$lineDot){

    $mazePositions=[];
    foreach ($positions as $position){

            if(in_array($position,$lineDot)){
                $mazePositions[]=$position;
            }
    }
    return $mazePositions;
}

/**
 *  计算最短路线
 *
 * 迷宫平面坐标系
 * @param $line
 * 待用的点
 * @param $canReOpen
 * 开始的点
 * @param $startDot
 * 所有迷宫的可走的点
 * @param $mazePositions
 * 不能放置的点比如平面坐标系外的点
 * @param $notPlacedDot
 * 迷宫终点
 * @param $endDot
 * 没用到坐标系的宽
 * @param $n
 * 初始值默认1 最终会达到 $stepCount后会重置
 * @param $count
 * 存放一个点的走 $stepCount 步所有可能性类似于这样的数组 json_decode({"0":[1,0],"10":[[1,1]],"11":[[1,2],[2,1]],"12":[[2,2],[0,2]],"22":[[3,2],[3,2]],"02":[[0,3]],"21":[[2,2],[3,1]],"31":[[3,2],[3,0]]}',true)
 * @param $nextStep
 * 走的过程中不能放置的点
 * @param $extraNotPlaceDot
 * @param $stepCount
 * @return array
 */
function getShortLine($line,$canReOpen,$startDot,$mazePositions,$notPlacedDot,$endDot,$n,$count,$nextStep,$extraNotPlaceDot,$stepCount){

    $dotWrapper=GetDotWrappers($startDot);  //一个点的上下左右点
    $allOpen = array_reduce($canReOpen, 'array_merge', array()); //待用点
    $arr=[];//周围符合条件的点
    $notPlacedDotAll =array_merge($notPlacedDot,$extraNotPlaceDot);
    foreach ($dotWrapper as $dot){
        if(in_array($dot,$mazePositions)&&!in_array($dot,$line)&&!in_array($dot,$allOpen)&&!in_array($dot,$notPlacedDotAll)){
            $arr[distance($dot,$endDot)][]=$dot;
        }
    }

    if($count==1){//首次进入父节点

        if($startDot==$endDot){
            return $line;
        }
        if(empty($arr)){//死点
            array_pop($line);
            $extraNotPlaceDot[]=$startDot;
            $nextStartDot = $line[count($line)-1];

        }else{

            ksort($arr);//按距离大小升序排序
            $arr = array_reduce($arr, 'array_merge', array());
            $canReOpen=[];
            if(!empty($arr)){
                $canReOpen[] = array_values($arr);
            }
            $nextSteps=[];//父节点走$stepCount步,周围所有可能走的点,是一个二维数组 类似于这样json_decode([{"0":[1,0],"10":[[1,1]],"11":[[1,2],[2,1]],"12":[[2,2],[0,2]],"22":[[3,2],[3,2]],"02":[[0,3]],"21":[[2,2],[3,1]],"31":[[3,2],[3,0]]}]',true)
            $count++;
            do{//求周围点的可能
                $nextStep=[];
                $nextStartDot=array_shift($arr);//依次取出最小距离的作为开始点
                if($nextStartDot==$endDot){
                    array_push($line,$nextStartDot);
                    return $line;
                }
                $nextStep[0]=$nextStartDot;//父顶点
                //调用 getShortLine 进入到if($count==1){}else{} 的else 代码块。求走$stepCount的所有可能的点
                $nextSteps[] = getShortLine($line,$canReOpen,$nextStartDot,$mazePositions,$notPlacedDot,$endDot,$n,$count,$nextStep,$extraNotPlaceDot,$stepCount);

            }while(!empty($arr));

            $result=[];
            foreach ($nextSteps as $step){
                if(isset($step[0])){
                    $ar=[];
                    $item=$step[0];
                    unset($step[0]);
                    $parent=[];
                    $result=linkTable($result,$step,$item,$item,$ar,$parent);//将结果转化为链表的结构
                }
            }
            $nextSteps=$result;
            if(empty($nextSteps)){
                array_pop($line);
                $extraNotPlaceDot[]=$startDot;
                $nextStartDot = $line[count($line)-1];
            }else{
                $full=[];
                $notFull=[];
                foreach ($nextSteps as $k1=>$temp){
                    if(count($temp)==$stepCount){//走完$stepCount的点
                        $full[$k1]=$temp;
                    }else{//没走完$stepCount的点
                        $notFull[$k1]=$temp;
                    }
                }
                if(!empty($full)){//优先使用走完$stepCount步的点
                    $temps=[];
                    foreach ($full as $key=>$tmp){
                        $end=$tmp[count($tmp)-1];
                        $distance=distance($end,$endDot);
                        $temps[$distance]=$tmp;
                    }
                }else{
                    $temps=[];
                    foreach ($notFull as $key=>$tmp){
                        $end=$tmp[count($tmp)-1];
                        $distance=distance($end,$endDot);
                        $temps[$distance]=$tmp;
                    }
                }

                ksort($temps);//按距离大小升序排序
                $steps=array_shift($temps);//取出最近的一个组点
                $nextStartDot=$steps[count($steps)-1];//最后一个点作为开始点
                $line=array_merge($line,$steps);
                if($nextStartDot==$endDot){
                    return $line;
                }
            }

        }
        //继续下一个点重复以上步骤
        $count=1;
        return getShortLine($line,$canReOpen,$nextStartDot,$mazePositions,$notPlacedDot,$endDot,$n,$count,$nextStep,$extraNotPlaceDot,$stepCount);
    }else{//求每一个父顶点下的所有可能点

        if($startDot==$endDot){
            return $nextStep;
        }
        if($count<=$stepCount){
            if(empty($arr)){//死点
                $extraNotPlaceDot[]=$startDot;//这个点不能放
                foreach ($nextStep as $key=>&$next){//把这个点移出去, $nextStep 属于结构类似与这样 json_decode({"0":[1,0],"10":[[1,1]],"11":[[1,2],[2,1]],"12":[[2,2],[0,2]],"22":[[3,2],[3,2]],"02":[[0,3]],"21":[[2,2],[3,1]],"31":[[3,2],[3,0]]}',true)
                    if($startDot==$next){
                        unset($nextStep[$key]);
                        continue;
                    }
                    if(in_array($startDot,$next)){
                        unset($next[array_search($startDot,$next)]);

                        if(empty($next)){
                            unset($nextStep[$key]);
                        }else{
                            $next=array_values($next);
                        }
                    }
                }
                return $nextStep;
            }else{
                ksort($arr);//按距离大小升序排序
                $arr = array_reduce($arr, 'array_merge', array());

                $canReOpen[] = array_values($arr);

                do{//继续改点的分裂直到达到$stepCount 一个点可能分裂为1个两个或三个
                    $count_tmp=$count;
                    $nextStartDot=array_shift($arr);
                    $nextStep[$startDot[0].$startDot[1]][]=$nextStartDot;

                    $count_tmp++;
                    $nextStep=getShortLine($line,$canReOpen,$nextStartDot,$mazePositions,$notPlacedDot,$endDot,$n,$count_tmp,$nextStep,$extraNotPlaceDot,$stepCount);

                }while(!empty($arr));

                return $nextStep=array_map(function ($val){
                    if(isset($val[0])&&!is_array($val[0])){//父节点第一个点
                        return $val;
                    }
                    return array_values(array_unique($val,SORT_REGULAR));
                },$nextStep);

            }
        }else{

            if(empty($arr)){//死点
                $extraNotPlaceDot[]=$startDot;//这个点不能放
            }
            return $nextStep;
        }
    }
}


function getAllHtml($positions,$lineDot,$n){
    $str="<table border='1'>";

    foreach (array_chunk($positions,$n+1) as $row){
        $str.="<tr>";
        foreach ($row as $tr){
            if(in_array($tr,$lineDot)){

                $str.="<td style='color: white;background-color: red'>{$tr[0]},{$tr[1]}</td>";


            }else{
                $str.="<td>{$tr[0]},{$tr[1]}</td>";
            }
        }
        $str.="<tr>";

    };
    $str.="</table>";
    return $str;
}
function getHtml($positions,$lineDot,$shortLine,$n){
    $str="<table border='1'>";

    foreach (array_chunk($positions,$n+1) as $row){
        $str.="<tr>";
        foreach ($row as $tr){
            if(in_array($tr,$lineDot)){
                if(in_array($tr,$shortLine)){
                    $str.="<td style='color: white;background-color: blue'>{$tr[0]},{$tr[1]}</td>";
                }else{
                    $str.="<td style='color: white;background-color: red'>{$tr[0]},{$tr[1]}</td>";
                }

            }else{
                $str.="<td>{$tr[0]},{$tr[1]}</td>";
            }
        }
        $str.="<tr>";

    };
    $str.="</table>";
    return $str;
}

function linkTable($result,$steps,$item,$start,$ar,$parent){

    if(isset($steps[$item[0].$item[1]])&&!empty($steps[$item[0].$item[1]])){
        $items=$steps[$item[0].$item[1]];
        $length=count($items);
        for ($i=0;$i<$length;$i++){
            if(!in_array($items[$i],$ar)){//避免形成一个环
                $parent[]=$items[$i];
                $ar[]=$items[$i];
                $item=$items[$i];
                $result=linkTable($result,$steps,$item,$start,$ar,$parent);
                array_pop($parent);
                $ar=$parent;
            }
        }
        return array_values(array_unique($result,SORT_REGULAR ));
    }else{
        array_unshift($ar,$start);
        $result[]=$ar;
        return $result;
    }
}
function distance($start,$end){
    return abs($end[0]-$start[0])+abs($end[1]-$start[1]);
}

function notPlacedDot($positions,$n)
{
    
    $notPlacedDot=[];
    foreach ($positions as $position){
        $dotWrapper=GetDotWrappers($position);

        foreach ($dotWrapper as $dot){
            if($dot[0]<0||$dot[1]<0||$dot[0]>$n||$dot[1]>$n){
                $notPlacedDot[]=$dot;
            }
        }
    }
    return $notPlacedDot;
}

/**
 * 是否是坏点
 * @param $dotWrapper
 * @param $placedDot
 * @param $notPlacedDot
 * @return bool
 */
function badDot($position,$placedDot,$notPlacedDot,$n){
    
    $dotWrapper=GetDotWrappers($position);
    $i=0;
    foreach ($dotWrapper as $dot){
        if($dot[0]<0||$dot[1]<0||$dot[1]>$n||in_array($dot,$placedDot)||in_array($dot,$notPlacedDot)){
            $i++;
        }
    }
    if($i==4){
        return true;
    }
    return false;

}


function GetDotWrappers($placementEd){
    $top = calculateXY($placementEd[0],$placementEd[1],'top');
    $bottom = calculateXY($placementEd[0],$placementEd[1],'bottom');
    $left = calculateXY($placementEd[0],$placementEd[1],'left');
    $right = calculateXY($placementEd[0],$placementEd[1],'right');
    return [$top,$bottom,$left,$right];
}

function calculateXY($x,$y,$default='top')
{
    switch ($default){
        case 'top':
            $y=$y+1;
            break;
        case 'bottom':
            $y=$y-1;
            break;
        case 'left':
            $x=$x-1;
            break;
        case 'right':
            $x=($x+1);
            break;
        case 'left_top':
            $x=($x-1);
            $y=($y+1);
            break;
        case 'right_top':
            $x=($x+1);
            $y=($y+1);
            break;
        case 'right_bottom':
            $x=($x+1);
            $y=($y-1);
            break;
        case 'left_bottom':
            $x=($x-1);
            $y=($y-1);
            break;
    }

    return [$x,$y];
}

输出:

解迷宫
0,01,02,03,04,05,06,07,08,09,010,011,012,013,014,015,016,017,018,019,020,021,022,023,024,025,026,027,028,029,030,0
0,11,12,13,14,15,16,17,18,19,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,1
0,21,22,23,24,25,26,27,28,29,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,2
0,31,32,33,34,35,36,37,38,39,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,3
0,41,42,43,44,45,46,47,48,49,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,4
0,51,52,53,54,55,56,57,58,59,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,5
0,61,62,63,64,65,66,67,68,69,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,6
0,71,72,73,74,75,76,77,78,79,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,7
0,81,82,83,84,85,86,87,88,89,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,8
0,91,92,93,94,95,96,97,98,99,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,9
0,101,102,103,104,105,106,107,108,109,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,1030,10
0,111,112,113,114,115,116,117,118,119,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,1121,1122,1123,1124,1125,1126,1127,1128,1129,1130,11
0,121,122,123,124,125,126,127,128,129,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,1221,1222,1223,1224,1225,1226,1227,1228,1229,1230,12
0,131,132,133,134,135,136,137,138,139,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,1321,1322,1323,1324,1325,1326,1327,1328,1329,1330,13
0,141,142,143,144,145,146,147,148,149,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,1421,1422,1423,1424,1425,1426,1427,1428,1429,1430,14
0,151,152,153,154,155,156,157,158,159,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,1521,1522,1523,1524,1525,1526,1527,1528,1529,1530,15
0,161,162,163,164,165,166,167,168,169,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,1621,1622,1623,1624,1625,1626,1627,1628,1629,1630,16
0,171,172,173,174,175,176,177,178,179,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,1721,1722,1723,1724,1725,1726,1727,1728,1729,1730,17
0,181,182,183,184,185,186,187,188,189,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,1821,1822,1823,1824,1825,1826,1827,1828,1829,1830,18
0,191,192,193,194,195,196,197,198,199,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,1921,1922,1923,1924,1925,1926,1927,1928,1929,1930,19
0,201,202,203,204,205,206,207,208,209,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019,2020,2021,2022,2023,2024,2025,2026,2027,2028,2029,2030,20
0,211,212,213,214,215,216,217,218,219,2110,2111,2112,2113,2114,2115,2116,2117,2118,2119,2120,2121,2122,2123,2124,2125,2126,2127,2128,2129,2130,21
0,221,222,223,224,225,226,227,228,229,2210,2211,2212,2213,2214,2215,2216,2217,2218,2219,2220,2221,2222,2223,2224,2225,2226,2227,2228,2229,2230,22
0,231,232,233,234,235,236,237,238,239,2310,2311,2312,2313,2314,2315,2316,2317,2318,2319,2320,2321,2322,2323,2324,2325,2326,2327,2328,2329,2330,23
0,241,242,243,244,245,246,247,248,249,2410,2411,2412,2413,2414,2415,2416,2417,2418,2419,2420,2421,2422,2423,2424,2425,2426,2427,2428,2429,2430,24
0,251,252,253,254,255,256,257,258,259,2510,2511,2512,2513,2514,2515,2516,2517,2518,2519,2520,2521,2522,2523,2524,2525,2526,2527,2528,2529,2530,25
0,261,262,263,264,265,266,267,268,269,2610,2611,2612,2613,2614,2615,2616,2617,2618,2619,2620,2621,2622,2623,2624,2625,2626,2627,2628,2629,2630,26
0,271,272,273,274,275,276,277,278,279,2710,2711,2712,2713,2714,2715,2716,2717,2718,2719,2720,2721,2722,2723,2724,2725,2726,2727,2728,2729,2730,27
0,281,282,283,284,285,286,287,288,289,2810,2811,2812,2813,2814,2815,2816,2817,2818,2819,2820,2821,2822,2823,2824,2825,2826,2827,2828,2829,2830,28
0,291,292,293,294,295,296,297,298,299,2910,2911,2912,2913,2914,2915,2916,2917,2918,2919,2920,2921,2922,2923,2924,2925,2926,2927,2928,2929,2930,29
0,301,302,303,304,305,306,307,308,309,3010,3011,3012,3013,3014,3015,3016,3017,3018,3019,3020,3021,3022,3023,3024,3025,3026,3027,3028,3029,3030,30

迷宫路线
0,01,02,03,04,05,06,07,08,09,010,011,012,013,014,015,016,017,018,019,020,021,022,023,024,025,026,027,028,029,030,0
0,11,12,13,14,15,16,17,18,19,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,1
0,21,22,23,24,25,26,27,28,29,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,2
0,31,32,33,34,35,36,37,38,39,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,3
0,41,42,43,44,45,46,47,48,49,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,4
0,51,52,53,54,55,56,57,58,59,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,5
0,61,62,63,64,65,66,67,68,69,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,6
0,71,72,73,74,75,76,77,78,79,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,7
0,81,82,83,84,85,86,87,88,89,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,8
0,91,92,93,94,95,96,97,98,99,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,9
0,101,102,103,104,105,106,107,108,109,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,1030,10
0,111,112,113,114,115,116,117,118,119,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,1121,1122,1123,1124,1125,1126,1127,1128,1129,1130,11
0,121,122,123,124,125,126,127,128,129,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,1221,1222,1223,1224,1225,1226,1227,1228,1229,1230,12
0,131,132,133,134,135,136,137,138,139,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,1321,1322,1323,1324,1325,1326,1327,1328,1329,1330,13
0,141,142,143,144,145,146,147,148,149,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,1421,1422,1423,1424,1425,1426,1427,1428,1429,1430,14
0,151,152,153,154,155,156,157,158,159,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,1521,1522,1523,1524,1525,1526,1527,1528,1529,1530,15
0,161,162,163,164,165,166,167,168,169,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,1621,1622,1623,1624,1625,1626,1627,1628,1629,1630,16
0,171,172,173,174,175,176,177,178,179,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,1721,1722,1723,1724,1725,1726,1727,1728,1729,1730,17
0,181,182,183,184,185,186,187,188,189,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,1821,1822,1823,1824,1825,1826,1827,1828,1829,1830,18
0,191,192,193,194,195,196,197,198,199,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,1921,1922,1923,1924,1925,1926,1927,1928,1929,1930,19
0,201,202,203,204,205,206,207,208,209,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019,2020,2021,2022,2023,2024,2025,2026,2027,2028,2029,2030,20
0,211,212,213,214,215,216,217,218,219,2110,2111,2112,2113,2114,2115,2116,2117,2118,2119,2120,2121,2122,2123,2124,2125,2126,2127,2128,2129,2130,21
0,221,222,223,224,225,226,227,228,229,2210,2211,2212,2213,2214,2215,2216,2217,2218,2219,2220,2221,2222,2223,2224,2225,2226,2227,2228,2229,2230,22
0,231,232,233,234,235,236,237,238,239,2310,2311,2312,2313,2314,2315,2316,2317,2318,2319,2320,2321,2322,2323,2324,2325,2326,2327,2328,2329,2330,23
0,241,242,243,244,245,246,247,248,249,2410,2411,2412,2413,2414,2415,2416,2417,2418,2419,2420,2421,2422,2423,2424,2425,2426,2427,2428,2429,2430,24
0,251,252,253,254,255,256,257,258,259,2510,2511,2512,2513,2514,2515,2516,2517,2518,2519,2520,2521,2522,2523,2524,2525,2526,2527,2528,2529,2530,25
0,261,262,263,264,265,266,267,268,269,2610,2611,2612,2613,2614,2615,2616,2617,2618,2619,2620,2621,2622,2623,2624,2625,2626,2627,2628,2629,2630,26
0,271,272,273,274,275,276,277,278,279,2710,2711,2712,2713,2714,2715,2716,2717,2718,2719,2720,2721,2722,2723,2724,2725,2726,2727,2728,2729,2730,27
0,281,282,283,284,285,286,287,288,289,2810,2811,2812,2813,2814,2815,2816,2817,2818,2819,2820,2821,2822,2823,2824,2825,2826,2827,2828,2829,2830,28
0,291,292,293,294,295,296,297,298,299,2910,2911,2912,2913,2914,2915,2916,2917,2918,2919,2920,2921,2922,2923,2924,2925,2926,2927,2928,2929,2930,29
0,301,302,303,304,305,306,307,308,309,3010,3011,3012,3013,3014,3015,3016,3017,3018,3019,3020,3021,3022,3023,3024,3025,3026,3027,3028,3029,3030,30