矩阵算法大全(《矩阵计算》)

导语：经典算法题：01 矩阵

一、题目

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

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

示例 1: 输入:

0 0 00 1 00 0 0输出:

0 0 00 1 00 0 0示例 2: 输入:

0 0 00 1 01 1 1输出:

0 0 00 1 01 2 1

二、思路

元素0和自身的距离是0，元素1和0的距离等于0到1的距离。

用一个标记数组记录每个位置是否已经计算过距离。

初始化结果集和队列，遍历矩阵找到所有等于0的位置，结果集对应位置赋值0并且坐标入队。计算过距离的位置标记。

使用广搜，队列中元素出队后向四个方向分别搜索一次寻找1，如果搜索位置存在1则记录结果集距离为结果集中搜索源点的值+1，并且入队、标记。

三、实现

class Solution {

public int[][] updateMatrix(int[][] matrix) {

if (matrix == null || matrix.length == 0) {

return null;

}

int m = matrix.length;

int n = matrix[0].length;

int[][] res = new int[m][n];

boolean[][] visited = new boolean[m][n];

Queue<int[]> queue = new LinkedList<>();

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (matrix[i][j] == 0) {

res[i][j] = 0;

visited[i][j] = true;

queue.offer(new int[]{i, j});

}

}

}

int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//上下左右

while (!queue.isEmpty()) {

int[] tmp = queue.poll();

int i = tmp[0];

int j = tmp[1];

for (int k = 0; k < 4; k++) {

int di = i + direction[k][0];

int dj = j + direction[k][1];

if (di >= 0 && di < m && dj >= 0 && dj < n && !visited[di][dj]) {

res[di][dj] = res[i][j] + 1;

visited[di][dj] = true;

queue.offer(new int[]{di, dj});

}

}

}

return res;

}

}

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小若创作整理编辑！