C++ BFS / Greedy


  • 0

    BFS

    // OJ: https://leetcode.com/problems/01-matrix
    // Auther: github.com/lzl124631x
    // Time: O(MN)
    // Space: O(MN)
    class Solution {
    public:
      vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return matrix;
        int M = matrix.size(), N = matrix[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < M; ++i) {
          for (int j = 0; j < N; ++j) {
            if (!matrix[i][j]) q.emplace(i, j);
            else matrix[i][j] = INT_MAX;
          }
        }
        int dirs[][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};
        while (q.size()) {
          auto p = q.front();
          q.pop();
          for (auto dir : dirs) {
            int x = p.first + dir[0], y = p.second + dir[1];
            if (x >= 0 && x < M && y >= 0 && y < N && matrix[x][y] == INT_MAX) {
              matrix[x][y] = matrix[p.first][p.second] + 1;
              q.emplace(x, y);
            }
          }
        }
        return matrix;
      }
    };
    

    Greedy

    // OJ: https://leetcode.com/problems/01-matrix
    // Auther: github.com/lzl124631x
    // Time: O(MN)
    // Space: O(1)
    // Ref: https://discuss.leetcode.com/topic/83472/18-line-c-dp-solution-o-n-easy-to-understand
    class Solution {
    public:
      vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return matrix;
        int M = matrix.size(), N = matrix[0].size();
        for (int i = 0; i < M; ++i) {
          for (int j = 0; j < N; ++j) {
            if (matrix[i][j])  matrix[i][j] = INT_MAX;
          }
        }
        int dirs[][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};
        for (int t = 0; t <= 1; ++t) {
          for (int i = t ? 0 : M - 1; t ? i < M : i >= 0; t ? ++i : --i) {
            for (int j = t ? 0 : N - 1; t ? j < N : j >= 0; t ? ++j : --j) {
              if (!matrix[i][j]) continue;
              for (auto d : dirs) {
                int x = i + d[0], y = j + d[1];
                if (x >= 0 && x < M && y >= 0 && y < N && matrix[x][y] != INT_MAX)
                  matrix[i][j] = min(matrix[i][j], matrix[x][y] + 1);
              }
            }
          }
        }
        return matrix;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.