Problem
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 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.
Solution 1: DP
Two passes:
- down, right
- up, left
Time complexity: O(mn)
Space complexity: O(mn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 132 ms class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<vector<int>> ans(m, vector<int>(n, INT_MAX - m * n)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j]) { if (i > 0) ans[i][j] = min(ans[i][j], ans[i - 1][j] + 1); if (j > 0) ans[i][j] = min(ans[i][j], ans[i][j - 1] + 1); } else { ans[i][j] = 0; } for (int i = m - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) { if (i < m - 1) ans[i][j] = min(ans[i][j], ans[i + 1][j] + 1); if (j < n - 1) ans[i][j] = min(ans[i][j], ans[i][j + 1] + 1); } return ans; } }; |
Solution 2: BFS
Start from all 0 cells and find shortest paths to rest of the cells.
Time complexity: O(mn)
Space complexity: O(mn)
|
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 |
// Author: Huahua // Running time: 136 ms class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { const int m = matrix.size(); const int n = matrix[0].size(); queue<pair<int, int>> q; vector<vector<int>> seen(m, vector<int>(n, 0)); vector<vector<int>> ans(m, vector<int>(n, INT_MAX)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j] == 0) { q.push({i, j}); seen[i][j] = 1; } vector<int> dirs{0, -1, 0, 1, 0}; int steps = 0; while (!q.empty()) { int size = q.size(); while (size--) { auto pair = q.front(); q.pop(); int i = pair.first; int j = pair.second; ans[i][j] = steps; for (int k = 0; k < 4; ++k) { int x = j + dirs[k]; int y = i + dirs[k + 1]; if (x < 0 || x >= n || y < 0 || y >= m || seen[y][x]) continue; seen[y][x] = 1; q.push({y, x}); } } ++steps; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment