王者編程大賽之二 — 蓄水池

Me_Kun 發布于2019-07-01 12:36 / 2997人閱讀

摘要：相關文章王者編程大賽之一王者編程大賽之三背包王者編程大賽之四約瑟夫環王者編程大賽之五最短路徑

首發于 樊浩柏科學院

自如寓打算門口用磚頭圍立一個蓄水池子，從上面看凹凸不平，凹的地方會有積水。那如果用數字代表每個磚頭的高度，就形成一個二維數據（如示例），請問這個池子能存儲多少單位的水？

例如二維數組為：

9 9 9 9
3 0 0 9
7 8 2 6
時，答案是中間的 0,0 位置可以存儲 2（因為其外面最低是 2）個單位的水，因此答案為 2 + 2 = 4。

示例：
輸入：[1 1 1 1,1 0 0 1,1 1 1 1]
輸出：2
輸入：[12 11 12 0 13,12 9 8 12 12,13 10 0 3 15,19 4 4 7 15,19 4 3 0 15,12 13 10 15 13]
輸出：58

解題思路

這道題是所有題中困惑我時間最長的題，一開始思維禁錮在想直接通過找到每塊磚的四周有效最低磚高度 $H_{min}$，然后這塊磚所剩的水為 $w[i][j] = H_{min}-h[i][j]$($h[i][j]$ 為磚的高度，i 和 j 為磚的位置坐標)，因此蓄水池能蓄下的水為 $sum_{i=1}^nsum_{j=1}^n w[i][j]$。經過一番嘗試，發現尋找某塊磚四周最低有效磚邏輯比較復雜，且不易理解，又嘗試過使用回溯算法尋找出池子中的所有連通圖，但是也未有果。

最后，發現基礎平臺一位同學的實現思路很清晰，我認為他的實現是最合適的，所以研究了一下。該實現中機智地采用逆向思維，首先往池子注滿水（最高磚的高度），然后再通過條件判定每塊磚是否需要進行漏水，一直到沒有磚需要進行漏水操作。

實現思路如下：

找出高度最高的磚，高度記為 $H_{max}$；

對除去邊界的磚進行注水操作，每塊磚加水量為 $w[i][j] = H_{max} - h[i][j]$（$h[i][j]$ 為磚的高度）；

對某塊磚進行漏水操作，只要這塊磚有盛水且上下左右相鄰的 4 塊磚高度和盛水量之和小于這塊磚高度和盛水量之和，則需要進行一次漏水，漏水條件可以描述為 $w[i][j] > 0$ && $h[i][j-1] + w[i][j-1] < h[i][j] + w[i][j]$（該條件為磚左側相鄰的漏水條件，右、上、下同理可得）；

持續漏水操作，一直重復步驟 3 直至沒有磚需要進行漏水操作；

求和磚的盛水量，$sum_{i=1}^nsum_{j=1}^n w[i][j]$ 即為水池的蓄水量；

算法流程圖示如下：

編碼實現

實現的類結構如下，特殊的方法已提取出，并將一一詳細說明。

row = count($data);
        $this->col = count($data[0]);

        foreach ($data as $row => $rowArray) {
            foreach ($rowArray as $col => $height) {
                $height = (int)$height;
                $this->gridArray[$row][$col]["height"] = $height;
                $this->gridArray[$row][$col]["water"] = 0;
                //獲取最高磚的高度
                if ($this->maxHeight < $height) {
                    $this->maxHeight = $height;
                }
            }
        }
    }
    
    //判斷是否是水池邊界
    public function isBorder($row, $col)
    {
        if ($row == 0
            || $row == $this->row - 1
            || $col == 0
            || $col == $this->col - 1
        ) {
            return true;
        }

        return false;
    }

    public function run()
    {
        $this->addWater();

        while ($this->removeWater()) ;

        return $this->collect();
    }
}

注水操作：

public function addWater()
{
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            if (!$this->isBorder($row, $col)) {
                $this->gridArray[$row][$col]["water"] = $this->maxHeight - $this->gridArray[$row][$col]["height"];
            }
        }
    }
}

漏水操作：

public function removeWater()
{
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            if ($this->canRemove($row, $col)) {
                return true;
            }
        }
    }

    return false;
}

漏水條件實現如下：

public function canRemove($row, $col)
{
    $can = false;

    if ($this->gridArray[$row][$col]["water"] > 0) {
        //上
        if ($this->gridArray[$row][$col]["water"] + $this->gridArray[$row][$col]["height"] >
            $this->gridArray[$row - 1][$col]["water"] + $this->gridArray[$row - 1][$col]["height"]) {
            $this->gridArray[$row][$col]["water"] =
                $this->gridArray[$row - 1][$col]["water"] + $this->gridArray[$row - 1][$col]["height"]
                - $this->gridArray[$row][$col]["height"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //右
        if ($this->gridArray[$row][$col]["water"] + $this->gridArray[$row][$col]["height"] >
            $this->gridArray[$row][$col + 1]["water"] + $this->gridArray[$row][$col + 1]["height"]) {
            $this->gridArray[$row][$col]["water"] =
                $this->gridArray[$row][$col + 1]["water"] + $this->gridArray[$row][$col + 1]["height"]
                - $this->gridArray[$row][$col]["height"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //下
        if ($this->gridArray[$row][$col]["water"] + $this->gridArray[$row][$col]["height"] >
            $this->gridArray[$row + 1][$col]["water"] + $this->gridArray[$row + 1][$col]["height"]) {
            $this->gridArray[$row][$col]["water"] =
                $this->gridArray[$row + 1][$col]["water"] + $this->gridArray[$row + 1][$col]["height"]
                - $this->gridArray[$row][$col]["height"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //左
        if ($this->gridArray[$row][$col]["water"] + $this->gridArray[$row][$col]["height"] >
            $this->gridArray[$row][$col - 1]["water"] + $this->gridArray[$row][$col - 1]["height"]) {
            $this->gridArray[$row][$col]["water"] =
                $this->gridArray[$row][$col - 1]["water"] + $this->gridArray[$row][$col - 1]["height"]
                - $this->gridArray[$row][$col]["height"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
    }

    return $can;
}

持續漏水操作：

public function run()
{
    while ($this->removeWater()) ;
}

求和磚的盛水量：

public function collect()
{
    $sum = 0;
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            $sum += $grid["water"];
        }
    }

    return $sum;
}

接收標準輸入處理并輸出結果：

$filter = function ($value) {
    return explode(" ", $value);
};

$pool = new Pool(array_map($filter, explode(",", $input)));
echo $pool->run(), PHP_EOL;

相似題目

Twitter 之前曾經出過類似蓄水池的筆試題，只不過本題是立體水池（二維數組），Twitter 蓄水池筆試題是平面水池（一維數組），解題復雜度也就降低了，當然 Twitter 蓄水池筆試題也可以采用本題的思想來實現，但是時間復雜度為 $O(n^2)$，采用我的Twitter技術面試失敗了的實現時間復雜度為 $O(n)$。

實現思路如下：

首先，用兩個指針（left 和 right）分別指向數組的第一個元素和最后一個元素，左指針從左向右遍歷，右指針從右向左遍歷；

初始化數組中一個元素（a[0]）為左邊遍歷得到的最大值（max_left），最后一個元素（a[a.length-1]）為從右邊遍歷得到的最大值（max_right）；

開始遍歷，遍歷結束條件為左指針不小于右指針；

如果左邊遍歷的最大值小于右邊遍歷的最大值，說明只要有水溝（即小于左邊最大值 max_left 的元素）就會有積水，因為右邊的最大值可以保證左邊水溝的積水不會流失掉；同樣，如果左邊遍歷的最大值不小于右邊遍歷的最大值，只要右邊有水溝（即小于右邊最大值 max_right 的元素）就會有積水；

具體實現，請直接參考 CuGBabyBeaR 文章。

總結

本題的蓄水池問題，如果理解了問題本質并逆向思維，將尋找某塊磚四周最低有效磚高度（尋找有效磚涉及到邊界擴散）轉化為判斷某塊磚是否需要漏水條件，那么問題就簡化很多了，那后續編碼也就很容易實現了，本文算法的時間復雜度為 $O(n^3)$。

相關文章 ?

王者編程大賽之一（2017-12-05）

[王者編程大賽之三 — 01背包](https://www.fanhaobai.com/201...

（2017-12-05）

王者編程大賽之四 — 約瑟夫環（2017-12-06）

王者編程大賽之五 — 最短路徑（2017-12-06）

云服務器 GPU云服務器世界編程大賽系列之二蓄水池水池

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31076.html

王者編程大賽之三 — 01背包

摘要：動態規劃概念動態規劃過程每次決策依賴于當前狀態，又隨即引起狀態的轉移。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環王者編程大賽之五最短路徑首發于樊浩柏科學院服務目前每月會對搬家師傅進行評級，根據師傅的評級排名結果，我們將優先保證最優師傅的全天訂單。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...

Cympros 2019-07-01 12:36 評論0 收藏0
王者編程大賽之五 — 最短路徑

摘要：由于是從頂點到的最短路徑，則有。算法流程根據最短路徑的最優子結構性質，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環首發于樊浩柏科學院自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具...

yuanzhanghu 2019-07-01 12:36 評論0 收藏0
王者編程大賽之一

摘要：首發于樊浩柏科學院本次王者編程大賽分為個組別，分別為研發測試移動戰場。本章只敘述前道相對簡單的題目，后續題目及解題思路將在王者編程大賽系列中列出。首發于樊浩柏科學院本次王者編程大賽分為 3 個組別，分別為研發、測試、移動戰場。這里只討論研發戰場所考的題目，本次大賽共有 7 道題，主要考查點為基礎算法，解題所用語言不做限制，但是需要在在線驗證平臺使用標準輸入并驗證通過，最后...

justCoding 2019-07-01 12:36 評論0 收藏0
JavaScript面向對象編程學習筆記---概念定義

摘要：子類繼承自父類的方法可以重新定義即覆寫，被調用時會使用子類定義的方法什么是多態青蛙是一個對象，金魚也是一個對象，青蛙會跳，金魚會游，定義好對象及其方法后，我們能用青蛙對象調用跳這個方法，也能用金魚對象調用游這個方法。 1、專用術語面向對象編程程序設計簡稱：OOP，在面向對象編程中常用到的概念有：對象、屬性、方法、類、封裝、聚合、重用與繼承、多態。 2、什么是對象？面向對象編程的重點...

mikasa 2019-08-23 11:48 評論0 收藏0