[LeetCode] 542. 01 Matrix

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/01-matrix/

Solution:
This question seems not hard, but it is not easy to pass the OJ. One way to do it is kind of brute force bfs: for each element, gradually expand the searching range step by step until find the 0 element. But it is not fast enough.

One way to improve it is to think it in an opposite way: starting from elements with 0 value. Then gradually expand it: the first layer of neighbors should be 1; then the next layer should be 2; ... It's kind of using memorization. See code below:

Code:

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        vector<vector<int>> res = matrix;
        if(!matrix.size() || !matrix.front().size()) return res;
        int m = matrix.size(), n = matrix.front().size();
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j]==0) q.push(tp(i, j));
                else res[i][j] = -1;
            }
        }
        vector<tp> d={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(q.size()){
            tp tt = q.front();
            int a = tt.first, b = tt.second;
            q.pop();
            for(auto t:d){
                int x = a + t.first, y = b + t.second;
                if(x>=0&&x<m&&y>=0&&y<n&&res[x][y]==-1){
                    res[x][y] = res[a][b] + 1;
                    q.push(tp(x,y));
                }
            }
        }
        return res;
    }
};