19. 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]]

Solution: (Brute Force BFS)

class Solution
{
public:
    int bfs(int a, int b, vector<vector<int>> &mat, vector<vector<int>> &vis)
    {
        int n = mat.size();
        int m = mat[0].size();

        queue<pair<int, int>> q;
        q.push({a, b});

        int dist = 0;

        vis[a][b] = 1;

        while (!q.empty())
        {
            int s = q.size();
            while (s > 0)
            {
                int i = q.front().first;
                int j = q.front().second;
                q.pop();
                if (i - 1 >= 0 && vis[i - 1][j] == 0)
                {
                    if (mat[i - 1][j] == 0)
                    {
                        return dist + 1;
                    }
                    vis[i - 1][j] = 1;
                    q.push({i - 1, j});
                }

                if (i + 1 < n && vis[i + 1][j] == 0)
                {
                    if (mat[i + 1][j] == 0)
                    {
                        return dist + 1;
                    }
                    vis[i + 1][j] = 1;
                    q.push({i + 1, j});
                }

                if (j - 1 >= 0 && vis[i][j - 1] == 0)
                {
                    if (mat[i][j - 1] == 0)
                    {
                        return dist + 1;
                    }
                    vis[i][j - 1] = 1;
                    q.push({i, j - 1});
                }

                if (j + 1 < m && vis[i][j + 1] == 0)
                {
                    if (mat[i][j + 1] == 0)
                    {
                        return dist + 1;
                    }
                    vis[i][j + 1] = 1;
                    q.push({i, j + 1});
                }
                s--;
            }
            dist++;
        }
        return dist;
    }

    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {
        vector<vector<int>> res;
        vector<int> v;
        int n = matrix.size();
        if (n == 0)
        {
            return res;
        }
        int m = matrix[0].size();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (matrix[i][j] == 0)
                {
                    v.push_back(0);
                }
                else
                {
                    vector<vector<int>> vis(n, vector<int>(m, 0));
                    int as = bfs(i, j, matrix, vis);
                    v.push_back(as);
                }
            }
            res.push_back(v);
            v.clear();
        }

        return res;
    }
};

Time complexity: O((r .c)^2)

Solution: (Optimized BFS [queue + BFS] )

class Solution
{
public:
    void bfs(queue<pair<int, int>> q, vector<vector<int>> &dist, vector<vector<int>> matrix)
    {

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

        while (!q.empty())
        {

            pair<int, int> p = q.front();
            q.pop();

            int x = p.first;
            int y = p.second;

            if (x - 1 >= 0 && matrix[x - 1][y] == 1)
            {
                if (dist[x][y] + 1 < dist[x - 1][y])
                {
                    dist[x - 1][y] = dist[x][y] + 1;
                    q.push({x - 1, y});
                }
            }

            if (x + 1 < n && matrix[x + 1][y] == 1)
            {
                if (dist[x][y] + 1 < dist[x + 1][y])
                {
                    dist[x + 1][y] = dist[x][y] + 1;
                    q.push({x + 1, y});
                }
            }

            if (y - 1 >= 0 && matrix[x][y - 1] == 1)
            {
                if (dist[x][y] + 1 < dist[x][y - 1])
                {
                    dist[x][y - 1] = dist[x][y] + 1;
                    q.push({x, y - 1});
                }
            }

            if (y + 1 < m && matrix[x][y + 1] == 1)
            {
                if (dist[x][y] + 1 < dist[x][y + 1])
                {
                    dist[x][y + 1] = dist[x][y] + 1;
                    q.push({x, y + 1});
                }
            }
        }
        return;
    }

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

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

        queue<pair<int, int>> q;
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (matrix[i][j] == 0)
                {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        bfs(q, dist, matrix);

        return dist;
    }
};