[leetcode题解]542.01 Matrix

给定一个由 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. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

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:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

思路比较简单,对矩阵中每个元素如果是1,则以其为起始节点进行广度优先搜索,搜索的时候记录深度,当搜到0时直接返回

因为总共有10000个元素,但是不知道多少行多少列,所以记录已经访问过的数组不要做成二维数组,用一维数组代替即可。

本方法比较简单粗暴,应该还有比较好的算法能巧妙的解决该问题,想到好的方法再来更新。

代码如下:

#include <queue>

using namespace std;

#define NDIR 4

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> res(matrix);
        int i = 0, j = 0;
        
        for (i = 0; i < rows; i++) {
            for (j = 0; j < matrix[i].size(); j++) {
                memset(visit, 0, sizeof(visit));
                if (matrix[i][j] == 1) {
                    res[i][j] = bfs(matrix, i, j, cols);
                } else {
                    res[i][j] = 0;
                }
            }
        }
        
        return res;
    }
private:
    int bfs(vector<vector<int>> &matrix, int x, int y, int cols) {
        queue<int> que;
        int i = 0;
        int tx = 0, ty = 0, depth = 0;
        
        que.push(x);
        que.push(y);
        que.push(0);
        
        while (!que.empty()) {
            x = que.front();
            que.pop();
            y = que.front();
            que.pop();
            depth = que.front();
            que.pop();
            
            for (i = 0; i < NDIR; i++) {
                tx = x + dirs[i][0];
                ty = y + dirs[i][1];
                
                if (tx < 0 || tx >= matrix.size() || ty < 0 || ty >= matrix[tx].size() || visit[tx * cols + ty])
                    continue;
                
                if (matrix[tx][ty] == 0)
                    return depth + 1;
                
                visit[tx * cols + ty] = true;
                que.push(tx);
                que.push(ty);
                que.push(depth + 1);
            }
        }
        
        return 0;
    }
    int dirs[NDIR][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    bool visit[10001];
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]542.01 Matrix

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/211.html

相关文章