public function test1(){
    $grid = [
        [1,1,1,1,1],
        [1,1,1,1,1],
        [1,1,1,1,1],
        [1,1,1,1,1],
        [1,1,1,1,1]
    ]; //网格
    $row = 2; // 初始x
    $col = 2; // 初始y
    $color = 3; // 结果颜色
    $old_color = $grid[$row][$col]; // 初始颜色
    $view_grid = []; // 已访问网格
    for($m = 0; $m < count($grid); $m++){
        for($n = 0; $n < count($grid[0]); $n++){
            $view_grid[$m][$n] = false;
        }
    }
    $borders = [];// 需要渲染的边界
    $this->dfs($grid,$row,$col,$view_grid,$borders,$old_color);
    for ($i = 0;$i < count($borders);$i++){
        $x = $borders[$i][0];
        $y = $borders[$i][1];
        $grid[$x][$y] = $color;
    }
    var_dump($grid);
}

public function dfs($grid,$x,$y,&$view,&$border,$old_color){
    $m = count($grid); // x总数
    $n = count($grid[0]); // y总数
    $direc = [[0,1],[0,-1],[1,0],[-1,0]]; // 右左上下四个方位坐标
    for($i = 0;$i < 4;$i++){
        $nx = $direc[$i][0] + $x; // 下一个查询的x坐标
        $ny = $direc[$i][1] + $y; // 下一个查询的y坐标
        // 如果下个x大于等于0 且 下个x小于x总数 且 下个y大于等于0 且下个y小于y总数 且 下个坐标颜色和初始颜色一致
        if(!($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n && isset($grid[$nx][$ny]) && $grid[$nx][$ny] == $old_color)){
            $border[] = [$x,$y];
        }else if(isset($view[$nx][$ny]) && $view[$nx][$ny] === false){
            $view[$nx][$ny] = true;
            $this->dfs($grid,$nx,$ny,$view,$border,$old_color);
        }
    }
}

https://leetcode-cn.com/problems/coloring-a-border/

标签: 算法

添加新评论