LeetCode 01 Matrix

LeetCode 01 Matrix 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.

给定一个0/1矩阵,要求每个点到其最近的0的距离。显然,如果自身是0的话,到最近的0的距离就是0,所以这里只需要求当cell不为0时,它到最近的0的距离。 显然是个BFS的题,从点(i,j)往外广度搜索,第一个遇到0时,走过的步数就是和0的最短距离;没遇到0时,不断的把点加入到队列中。 自定义一个MyPoint结构体,保存点的坐标,以及从出发点到该点的步数。注意本题不需要visited数组,visited数组的目的是保证在BFS时不走之前走过的点,但是BFS走过的路径肯定有那种没走之前走过的点的路径,这样的路径到达0的距离肯定会比走重复点的路径到达0的距离要短。所以不用visited也能找到最短距离。 代码如下: [cpp] typedef struct MyPoint { int x, y; int step; MyPoint(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {}; }; class Solution { private: int bfs(int i, int j, vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); MyPoint p(i, j, 0); queue<MyPoint> qp; qp.push(p); while (!qp.empty()) { p = qp.front(); if (matrix[p.x][p.y] == 0)return p.step; qp.pop(); if (p.x – 1 >= 0) { MyPoint tmp(p.x – 1, p.y, p.step + 1); qp.push(tmp); } if (p.x + 1 < m) { MyPoint tmp(p.x + 1, p.y, p.step + 1); qp.push(tmp); } if (p.y – 1 >= 0) { MyPoint tmp(p.x, p.y – 1, p.step + 1); qp.push(tmp); } if (p.y + 1 < n) { MyPoint tmp(p.x, p.y + 1, p.step + 1); qp.push(tmp); } } } public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int m = matrix.size(), n = 0; if (m > 0)n = matrix[0].size(); if (m == 0 || n == 0)return vector<vector<int>>(); vector<vector<int>> ans(m, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] != 0) { ans[i][j] = bfs(i, j, matrix); } } } return ans; } }; [/cpp] 本代码提交AC,用时276MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *