01 Matrix Solutions in C++

/// Source : https://leetcode.com/problems/01-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-09-29

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// BFS
/// Time Complexity: O(m*n)
/// Space Complexity: O(m*n)
class Solution {

private:
    const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m, n;

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        if(matrix.size() == 0 || matrix[0].size() == 0)
            return matrix;

        m = matrix.size();
        n = matrix[0].size();

        vector<vector<int>> res(m, vector<int>(n, INT_MAX));
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0)
                    res[i][j] = 0;

        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0)
                    bfs(matrix, i, j, res);

        return res;
    }

    void bfs(const vector<vector<int>>& matrix, int sx, int sy,
            vector<vector<int>>& res){

        queue<pair<int, int>> q;
        q.push(make_pair(sx * n + sy, 0));

        while(!q.empty()){
            int x = q.front().first / n;
            int y = q.front().first % n;
            int step = q.front().second;
            q.pop();

            for(int k = 0; k < 4; k ++){
                int newX = x + d[k][0], newY = y + d[k][1];
                if(inArea(newX, newY) && step + 1 < res[newX][newY]){
                    res[newX][newY] = step + 1;
                    q.push(make_pair(newX * n + newY, step + 1));
                }
            }
        }
    }

    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/01-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// BFS
/// No need to store pair in the queue:)
///
/// Time Complexity: O(m*n)
/// Space Complexity: O(m*n)
class Solution {

private:
    const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m, n;

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        if(matrix.size() == 0 || matrix[0].size() == 0)
            return matrix;

        m = matrix.size();
        n = matrix[0].size();

        vector<vector<int>> res(m, vector<int>(n, INT_MAX));
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0)
                    res[i][j] = 0;

        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0)
                    bfs(matrix, i, j, res);

        return res;
    }

    void bfs(const vector<vector<int>>& matrix, int sx, int sy,
            vector<vector<int>>& res){

        queue<int> q;
        q.push(sx * n + sy);

        while(!q.empty()){
            int x = q.front() / n;
            int y = q.front() % n;
            q.pop();

            for(int k = 0; k < 4; k ++){
                int newX = x + d[k][0], newY = y + d[k][1];
                if(inArea(newX, newY) && res[x][y] + 1 < res[newX][newY]){
                    res[newX][newY] = res[x][y] + 1;
                    q.push(newX * n + newY);
                }
            }
        }
    }

    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/01-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// BFS
/// Put all zero position in queue and only make one pass BFS :-)
///
/// Time Complexity: O(m*n)
/// Space Complexity: O(m*n)
class Solution {

private:
    const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m, n;

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        if(matrix.size() == 0 || matrix[0].size() == 0)
            return matrix;

        m = matrix.size();
        n = matrix[0].size();

        queue<int> q;
        vector<vector<int>> res(m, vector<int>(n, INT_MAX));
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0){
                    res[i][j] = 0;
                    q.push(i * n + j);
                }

        bfs(matrix, q, res);
        return res;
    }

    void bfs(const vector<vector<int>>& matrix, queue<int>& q,
             vector<vector<int>>& res){

        while(!q.empty()){
            int x = q.front() / n;
            int y = q.front() % n;
            q.pop();

            for(int k = 0; k < 4; k ++){
                int newX = x + d[k][0], newY = y + d[k][1];
                if(inArea(newX, newY) && res[x][y] + 1 < res[newX][newY]){
                    res[newX][newY] = res[x][y] + 1;
                    q.push(newX * n + newY);
                }
            }
        }
    }

    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/01-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(m*n)
/// Space Complexity: O(1)
class Solution {

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        if(matrix.size() == 0 || matrix[0].size() == 0)
            return matrix;

        int m = matrix.size(), n = matrix[0].size();

        vector<vector<int>> res(m, vector<int>(n, m + n + 1));
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0)
                    res[i][j] = 0;

        // top
        for(int i = 1; i < m; i ++)
            for(int j = 0; j < n; j ++)
                res[i][j] = min(1 + res[i - 1][j], res[i][j]);

        // left
        for(int i = 0; i < m; i ++)
            for(int j = 1; j < n; j ++)
                res[i][j] = min(1 + res[i][j - 1], res[i][j]);

        // bottom
        for(int i = m - 2; i >= 0; i --)
            for(int j = n - 1; j >= 0; j --)
                res[i][j] = min(1 + res[i + 1][j], res[i][j]);

        // right
        for(int i = m - 1; i >= 0; i --)
            for(int j = n - 2; j >= 0; j --)
                res[i][j] = min(1 + res[i][j + 1], res[i][j]);

        return res;
    }
};


int main() {

    return 0;
}