286. Walls and Gates

You are given am x n2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to itsnearestgate. If it is impossible to reach a gate, it should be filled withINF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

S: BFS

找到所有0点push进queue作为第一层，然后进行bfs.注意只有当dist + 1 < 当前值时才push

    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0) {
            return;
        }
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        int dist = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.push(make_pair(i, j));
                }
            }
        }
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int x1 = q.front().first;
                int y1 = q.front().second;
                q.pop();
                vector<int> dx{0, 1, 0, -1};
                vector<int> dy{1, 0, -1, 0};
                for (int j = 0; j < 4; ++j) {
                    int xi = x1 + dx[j];
                    int yi = y1 + dy[j];
                    if (xi < m && yi < n && xi >= 0 && yi >= 0
                        && dist + 1 < rooms[xi][yi]) {
                            rooms[xi][yi] = rooms[x1][y1] + 1;
                            q.push(make_pair(xi, yi));
                    }
                }
            }
        }
    }

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

S:BFS O(k*m*n)

将目标点0存储queue作为bfs第一层，将1点初始为INT_MAX. 依次更新queue内元素周围的点的值。只有当周围点的值大于当前值+1才更新，否则剪枝

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return vector<vector<int>> {};
        int n = matrix[0].size();
        vector<vector<int>> result(m, vector<int>(n, INT_MAX));
        queue<pair<int, int>> q;  //从0开始进行bfs更新周围元素
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    result[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n) {
                    if (result[x1][y1] > result[x][y] + 1) { //相邻元素的值比当前值大，需要更新,否则剪枝
                        result[x1][y1] = result[x][y] + 1;
                        q.push({x1, y1});
                    }
                }
            }
        }
        return result;
    }