发布于 5年前

PHP 判断某一个数,是否在n*m的二维数组中

这个二维数组,横竖都是递增的

代码:

<?php
$arr=[
    [2,4,6,9],
    [5,7,9,11],
    [7,9,12,13],
    [9,12,13,15],
];
$startDot=[0,0];//从第一个位置开始
$notPlacedDot=[];//不能放置的点
$canReOpen=[];//可以重新放置的点
$result=[];//对应的结果 [[3,1],[2,2]] 表示 $arr[3][1]  $arr[2][2] 有值12
$number=12;
echo json_encode(isExists($arr,$startDot,$canReOpen,$notPlacedDot,$result,$number));
function isExists($arr,$startDot,$canReOpen,$notPlacedDot,$result,$number){
    if(isset($arr[$startDot[0]],$arr[$startDot[0]][$startDot[1]])){//在数组中存在
        if(in_array($startDot,$notPlacedDot)||in_array($startDot,$result)){//这个点不满足要求或者已经计算出结果了
            if(!empty($canReOpen)){//是否有可放置的点
                $nextStartDot=array_pop($canReOpen);
                $result=isExists($arr,$nextStartDot,$canReOpen,$notPlacedDot,$result,$number);
            }
        }else{
            if($arr[$startDot[0]][$startDot[1]]==$number){//这个点满足要求
                $result[]=$startDot;
                if(!empty($canReOpen)){
                    $nextStartDot=array_pop($canReOpen);
                }else{
                    return $result;
                }
            } elseif($arr[$startDot[0]][$startDot[1]]>$number){//这个点不满足要求
                $notPlacedDot[]=$startDot;
                if(!empty($canReOpen)){
                    $nextStartDot=array_pop($canReOpen);
                }else{
                    return $result;
                }
            }else{//这个点小于$number 继续寻找下一个点
                $bottomRight=GetDotWrappers($startDot);
                $nextStartDot=array_pop($bottomRight);
                $canReOpen=array_merge($canReOpen,$bottomRight);
            }
            $result=isExists($arr,$nextStartDot,$canReOpen,$notPlacedDot,$result,$number);
        }
    }else{//跑到数组外面了
        $notPlacedDot[]=$startDot;
        if(!empty($canReOpen)){
            $nextStartDot=array_pop($canReOpen);
            $result=isExists($arr,$nextStartDot,$canReOpen,$notPlacedDot,$result,$number);
        }
    }
    return $result;
}

function GetDotWrappers($placementEd){

    $bottom = calculateXY($placementEd[0],$placementEd[1],'top');
    $right = calculateXY($placementEd[0],$placementEd[1],'right');
    return [$bottom,$right];
}
function calculateXY($x,$y,$default='top')
{
    switch ($default){
        case 'top':
            $y=$y+1;
            break;
        case 'right':
            $x=($x+1);
            break;
    }

    return [$x,$y];
}

输出:

[[3,1],[2,2]]
©2020 edoou.com   京ICP备16001874号-3