# [leetcode题解]542.01 Matrix

```0 0 0
0 1 0
0 0 0
```

```0 0 0
0 1 0
0 0 0
```

```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.

```#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];
};```