542. 01 Matrix

解題思路

要先從 mat[i][j] == 0 的那些位置開始探索周圍未被探索過的，所以用 queue 一個個找。

程式碼

struct Point
{
    int x, y;
};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> ans(mat.size(), vector<int> (mat[0].size(), -1));
        queue<Point> q;
        for(int i=0; i<mat.size(); i++)
        {
            for(int j=0; j<mat[0].size(); j++)
            {
                if(mat[i][j] == 0)
                {    
                    ans[i][j] = 0;
                    Point p; 
                    p.x = i;
                    p.y = j;
                    q.push(p);
                }
            }
        }
        int offset[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while(!q.empty())
        {
            for(int i=0; i<4; i++)
            {
                int newX = q.front().x + offset[i][0];
                int newY = q.front().y + offset[i][1];
                if(newX >= 0 && newX < mat.size() && newY >= 0 && newY < mat[0].size())
                {
                    if(ans[newX][newY] == -1)
                    {
                        ans[newX][newY] = ans[q.front().x][q.front().y] + 1;
                        Point p; 
                        p.x = newX;
                        p.y = newY;
                        q.push(p);
                    }
                }
            }
            q.pop();
        }
        return ans;
    }
};