文章目录
1. 题目
2. 思路
(1) BFS（超时）
- 遍历二维数组，当遇到1时，对其进行广度优先搜索，找到距离其最近的一个0，并返回路径长度。
- 在极端情况下容易超时。
(2) BFS优化
- 将二维数组中所有的0看作一个整体，同时加入队列，然后以这个整体为原点进行广度优先搜索，一层一层地向外扩展，路径长度逐层加1。
(3) 动态规划
3. 代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Test {
public static void main(String[] args) {
}
}
class Solution {
public int[][] updateMatrix(int[][] mat) {
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[0].length; j++) {
if (mat[i][j] == 1) {
mat[i][j] = bfs(mat, i, j);
}
}
}
return mat;
}
private int bfs(int[][] mat, int i, int j) {
int dist = 0;
Queue<int[]> queue = new LinkedList<>();
boolean[][] flag = new boolean[mat.length][mat[0].length];
queue.offer(new int[]{i, j});
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] index = queue.poll();
flag[index[0]][index[1]] = true;
if (index[0] > 0) {
if (mat[index[0] - 1][index[1]] == 0) {
return ++dist;
} else if (!flag[index[0] - 1][index[1]]) {
queue.offer(new int[]{index[0] - 1, index[1]});
}
}
if (index[0] < mat.length - 1) {
if (mat[index[0] + 1][index[1]] == 0) {
return ++dist;
} else if (!flag[index[0] + 1][index[1]]) {
queue.offer(new int[]{index[0] + 1, index[1]});
}
}
if (index[1] > 0) {
if (mat[index[0]][index[1] - 1] == 0) {
return ++dist;
} else if (!flag[index[0]][index[1] - 1]) {
queue.offer(new int[]{index[0], index[1] - 1});
}
}
if (index[1] < mat[0].length - 1) {
if (mat[index[0]][index[1] + 1] == 0) {
return ++dist;
} else if (!flag[index[0]][index[1] + 1]) {
queue.offer(new int[]{index[0], index[1] + 1});
}
}
}
dist++;
}
return dist;
}
}
class Solution1 {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length;
int col = mat[0].length;
int[][] res = new int[row][col];
boolean[][] flag = new boolean[row][col];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 0) {
queue.offer(new int[]{i, j});
flag[i][j] = true;
}
}
}
while (!queue.isEmpty()) {
int[] index = queue.poll();
int x = index[0];
int y = index[1];
if (x > 0 && !flag[x - 1][y]) {
res[x - 1][y] = res[x][y] + 1;
queue.offer(new int[]{x - 1, y});
flag[x - 1][y] = true;
}
if (x < row - 1 && !flag[x + 1][y]) {
res[x + 1][y] = res[x][y] + 1;
queue.offer(new int[]{x + 1, y});
flag[x + 1][y] = true;
}
if (y > 0 && !flag[x][y - 1]) {
res[x][y - 1] = res[x][y] + 1;
queue.offer(new int[]{x, y - 1});
flag[x][y - 1] = true;
}
if (y < col - 1 && !flag[x][y + 1]) {
res[x][y + 1] = res[x][y] + 1;
queue.offer(new int[]{x, y + 1});
flag[x][y + 1] = true;
}
}
return res;
}
}
class Solution2 {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length;
int col = mat[0].length;
int[][] res = new int[row][col];
for (int i = 0; i < row; i++) {
Arrays.fill(res[i], Integer.MAX_VALUE / 2);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 0) {
res[i][j] = 0;
}
}
}
// 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i > 0) {
res[i][j] = Math.min(res[i][j], res[i - 1][j] + 1);
}
if (j > 0) {
res[i][j] = Math.min(res[i][j], res[i][j - 1] + 1);
}
}
}
// 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
for (int i = row - 1; i >= 0; i--) {
for (int j = 0; j < col; j++) {
if (i < row - 1) {
res[i][j] = Math.min(res[i][j], res[i + 1][j] + 1);
}
if (j > 0) {
res[i][j] = Math.min(res[i][j], res[i][j - 1] + 1);
}
}
}
// 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
for (int i = 0; i < row; i++) {
for (int j = col - 1; j >= 0; j--) {
if (i > 0) {
res[i][j] = Math.min(res[i][j], res[i - 1][j] + 1);
}
if (j < col - 1) {
res[i][j] = Math.min(res[i][j], res[i][j + 1] + 1);
}
}
}
// 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i < row - 1) {
res[i][j] = Math.min(res[i][j], res[i + 1][j] + 1);
}
if (j < col - 1) {
res[i][j] = Math.min(res[i][j], res[i][j + 1] + 1);
}
}
}
return res;
}
}