542 01 Matrix 01 矩陣
Description:
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example:
Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]]
Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
Example 2:
Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.
題目描述:
給定一個由 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]]
提示:
給定矩陣的元素個數(shù)不超過 10000习勤。
給定矩陣中至少有一個元素是 0驮肉。
矩陣中的元素只在四個方向上相鄰: 上、下、左、右募谎。
思路:
BFS
可以先只查找左上的部分, 再查找右下的部分, 取兩部分到 0 的距離的最小值
時間復(fù)雜度 O(mn), 空間復(fù)雜度 O(1)
代碼:
C++:
class Solution
{
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix)
{
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> result(m, vector<int>(n, 0x3f3f3f3f));
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0) result[i][j] = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i - 1 >= 0) result[i][j] = min(result[i][j], result[i - 1][j] + 1);
if (j - 1 >= 0) result[i][j] = min(result[i][j], result[i][j - 1] + 1);
}
}
for (int i = m - 1; i >= 0; i--)
{
for (int j = n - 1; j >= 0; j--)
{
if (i + 1 < m) result[i][j] = min(result[i][j], result[i + 1][j] + 1);
if (j + 1 < n) result[i][j] = min(result[i][j], result[i][j + 1] + 1);
}
}
return result;
}
};
Java:
class Solution {
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) Arrays.fill(result[i], 0x3f3f3f3f);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0) result[i][j] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i - 1 >= 0) result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
if (j - 1 >= 0) result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i + 1 < m) result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
if (j + 1 < n) result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
}
}
return result;
}
}
Python:
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
m, n, d = len(matrix), len(matrix[0]), [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = [(i, j) for i in range(m) for j in range(n) if not matrix[i][j]]
visited = set(queue)
while queue:
x, y = queue.pop(0)
for dx, dy in d:
i, j = x + dx, y + dy
if -1 < i < m and -1 < j < n and (i, j) not in visited:
matrix[i][j] = matrix[x][y] + 1
visited.add((i, j))
queue.append((i, j))
return matrix