D94 733. Flood Fill

题目链接

733. Flood Fill

题目分析

给定一个二维表格，将给定的元素换成指定值。并且若上下左右4个方向有相同数字是也做同样的替换操作。如此反复。

思路

从指定的元素开始，先判断周围有没有到达边界。若有，则判断数值是否和原值相同。相同则把它存进待处理列表中。例如，上方是否有元素，有的话是否和当前位置值相同。相同则丢进待处理列表中。

最终代码

<?php
class Solution {
    protected $pendingCell = [];
    protected $image = [];
    protected $originalColor = null;

    /**
     * @param Integer[][] $image
     * @param Integer $sr
     * @param Integer $sc
     * @param Integer $newColor
     * @return Integer[][]
     */
    function floodFill($image, $sr, $sc, $newColor) {
        $this->image = $image;
        $this->originalColor = $image[$sr][$sc];
        $this->pendingCell[] = [$sr, $sc];
        while(count($this->pendingCell)){
            $point = array_shift($this->pendingCell);
            $this->fill($point[0], $point[1], $newColor);
        }
        return $this->image;
    }
    
    function fill($row, $col, $newColor){
        $this->image[$row][$col] = $newColor;
        if(isset($this->image[$row][$col+1])){
            if($this->image[$row][$col+1] == $this->originalColor && $this->image[$row][$col+1] != $newColor){
                $this->pendingCell[] = [$row, $col+1];
            }
        }
        
        if(isset($this->image[$row][$col-1])){
            if($this->image[$row][$col-1] == $this->originalColor && $this->image[$row][$col-1] != $newColor){
                $this->pendingCell[] = [$row, $col-1];
            }
        }
        
        if(isset($this->image[$row+1][$col])){
            if($this->image[$row+1][$col] == $this->originalColor && $this->image[$row+1][$col] != $newColor){
                $this->pendingCell[] = [$row+1, $col];
            }
        }
        
        if(isset($this->image[$row-1][$col])){
            if($this->image[$row-1][$col] == $this->originalColor && $this->image[$row-1][$col] != $newColor){
                $this->pendingCell[] = [$row-1, $col];
            }
        }
        
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。