今日算法之_135_01矩阵
前言
Github:https://github.com/HealerJean
1、01矩阵
给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
1.1、解题思路
四面八方走一趟
1.2、算法
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = matrix[i][j] == 0 ? 0 : 10000;
}
}
//左上角和左下角的的是又 其他方向遍历的时候截关
// 从左上角开始
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
}
}
}
// 从右下角开始
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i + 1 < m) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}
if (j + 1 < n) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
}
}
return dp;
}
1.3、测试
@Test
public void test() {
int[][] matrix = {
{0, 0, 0},
{0, 1, 0},
{1, 1, 1}
};
updateMatrix(matrix);
}