算法-矩阵

发表于 分类于 阅读次数：

01矩阵 LeetCode-542

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

Example 1:

1
2
3
4
5
6
7
8
9
Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

1
2
3
4
5
6
7
8
9
Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法：使用广度优先搜索，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    /**
     * @param Integer[][] $matrix
     * @return Integer[][]
     */
    function updateMatrix($matrix) {
        $res = []; //返回结果数组
        $queue = new SplQueue(); // 初始化队列，用来存储每层上的点
        foreach ($matrix as $i => $item) {
            foreach ($item as $j => $v) {
                if ($v === 0) { // 将题目转化为 0到其他点的距离
                    $res[$i][$j] = 0; // 0到自身的距离为0
                    $queue->enqueue([$i, $j]); // 将找到的0的坐标放在队列中
                }
            }
        }

        // BFS经典模板
        while (!$queue->isEmpty()) {
            // 取出某层上的点
            list($x, $y) = $queue->dequeue();
            // 加上四个方向的偏移量
            foreach ([[0, 1], [0, -1], [1, 0], [-1, 0]] as list($x_bias, $y_bias)) {
                $new_x = $x + $x_bias;
                $new_y = $y + $y_bias;
                // 判断扩展点的有效性
                if (0 <= $new_x && $new_x < count($matrix) && 0 <= $new_y && $new_y < count($matrix[0]) && !isset($res[$new_x][$new_y])) {
                    // 将新点的坐标和距离写入结果数组
                    $res[$new_x][$new_y] = $res[$x][$y] + 1;
                    // 将新扩展点加入队列
                    $queue->enqueue([$new_x, $new_y]);
                }
            }
        }
        // 二位结果集数组，按照key排序
        ksort($res);
        foreach ($res as &$item) {
            ksort($item);
        }
        return $res;
    }
}