php算法——接水滴

Question

php算法——接水滴

入职半年，还徘徊在无尽的增删改查和数据优化中的新手PHP程序员，最近被前端小哥带到进了算法的坑，做了很多算法题。
这题来自领扣网，比较有意思。
给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

说明:

m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。

示例：

给出如下 3x6 的高度图:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]

返回 4。

如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。

我的思路是：
能接水的体积是每层空缺的体积，但是在空缺的体积中，有一部分是带有缺口的。所以具体思路：

1.分层计算每层空缺体积
2.获取每层缺口体积
3.每层积水体积 = 空缺体积-缺口体积
4.累加每层积水体积

不知道有没有更好的思路。

Answer 1

1. 把没用的高杆子砍掉，比如两个4；
2. 终态是所有的中间各自都是最高点，比如图中中间4个全是3；
3. 终态初态相减即可。

Answer 2

<?php

class Trapping
{

public function water(){
    $arr = [
        [1,4,3,1,3,2],
        [3,2,1,3,2,4],
        [2,3,3,2,3,1]
    ];
    $shui = 0;
    //先获取层数，即二维数组中的最大值
    //获取数值最大值$max
    $b = [];
    foreach($arr as $key=>$value){
        $a=$arr[$key];
        $b = array_merge($a,$b);
        sort($b);
    }
    $max = $b[count($b)-1];

    for($i=0;$i<=$max-1;$i++){
        $eacharr = [];
        //获取分层的二维数组
        foreach($arr as $key =>$row){
            foreach($row as $key1=>$row1){
                if($row1-$i<0){
                    $row1 =0;
                }else{
                    $row1 = $row1-$i;
                }
                $eacharr[$key][$key1] = $row1;
            }
        } 
        //计算每层积水数       
        $shui += $this->each($eacharr);
    }
    return $shui;
}
/**
 * 计算每层积水数
 * @param  [array] $arr [每层的二维数组]
 * @return [int]      [每层积水数]
 */
public function each($arr){
    $shui = 0;
    //获取缺口模型
    foreach ($arr as $i => $row) {
        foreach($row as $j =>$row1){
            //$w 为该位高度，0表示该位置为空缺
            $w = $arr[$i][$j];
            if($w==0){
                //处于模型边界的空缺是缺口
                if( $i==0||$j == 0||$i == count($arr)-1||$j == count($row)-1){
                    $arr[$i][$j] = 'kou';
                    //与缺口相邻的空缺都是缺口，运用递归将其替换
                    $arr =  $this->kou($arr,$i,$j);
                }
            } 
        }
    }
    //计算该层剩余的空缺shu，即积水数
    foreach ($arr as $i => $row) {
        foreach($row as $j =>$row1){
            $w = $arr[$i][$j];
            if($w===0){
                $shui++;
            }  
        }
    }
    return $shui;
}
/**
 * 递归找出所有缺口
 * @param  [array]  $arr [模型二维数组]
 * @param  integer $i   [缺口坐标]
 * @param  integer $j   [缺口坐标]
 * @return [array]  $arr  [标识了缺口的二维数组]
 */
public function kou($arr,$i,$j){
        if(isset($arr[$i+1][$j])&&$arr[$i+1][$j]===0){
            $arr[$i+1][$j] = 'kou';
            $arr = $this->kou($arr,$i+1,$j);
        }elseif(isset($arr[$i-1][$j])&&$arr[$i-1][$j]===0){
            $arr[$i-1][$j] = 'kou';
            $arr =  $this->kou($arr,$i-1,$j);
        }elseif(isset($arr[$i][$j+1])&&$arr[$i][$j+1]===0){
            $arr[$i][$j+1] = 'kou';
            $arr = $this->kou($arr,$i,$j+1);
        }elseif(isset($arr[$i][$j-1])&&$arr[$i][$j-1]===0){
            $arr[$i][$j-1] = 'kou';
            $arr = $this->kou($arr,$i,$j-1);
        }else{
            return $arr;   
        } 
        return $arr;           
        
}

}