# 王者编程大赛算法之二 — 蓄水池

9 9 9 9
3 0 0 9
7 8 2 6

## 解题思路

1. 找出高度最高的砖，高度记为 $H_{max}$；
2. 对除去边界的砖进行注水操作，每块砖加水量为 $w[i][j] = H_{max} - h[i][j]$（$h[i][j]$ 为砖的高度）；
3. 对某块砖进行漏水操作，只要这块砖有盛水且上下左右相邻的 4 块砖高度和盛水量之和小于这块砖高度和盛水量之和，则需要进行一次漏水，漏水条件可以描述为 $w[i][j] > 0$ && $h[i][j-1] + w[i][j-1] < h[i][j] + w[i][j]$（该条件为砖左侧相邻的漏水条件，右、上、下同理可得）；
4. 持续漏水操作，一直重复步骤 3 直至没有砖需要进行漏水操作；
5. 求和砖的盛水量，$\sum{i=1}^n\sum{j=1}^n w[i][j]$ 即为水池的蓄水量；

## 编码实现

<?php

class Pool
{
public $gridArray = array(); public$maxHeight = 0;
public $row = 0; public$col = 0;

public function __construct(array $data) {$this->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)));

《L01 基础入门》

《L05 电商实战》

2年前 评论

@雷 夸张了

2年前 评论

10

34

59

8