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。]]>