01matrix

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

using namespace std;

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size();
    int n = mat[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    queue<pair<int, int>> q;

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

    vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        for (auto dir : dirs) {
            int newRow = curr.first + dir.first;
            int newCol = curr.second + dir.second;

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                if (dist[newRow][newCol] > dist[curr.first][curr.second] + 1) {
                    dist[newRow][newCol] = dist[curr.first][curr.second] + 1;
                    q.push({newRow, newCol});
                }
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
    vector<vector<int>> result = updateMatrix(mat);

    for (auto row : result) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Explanation:

• #include <iostream>: Includes the input/output stream for handling input and output operations.
• #include <vector>: Includes the vector container to work with dynamic arrays.
• #include <queue>: Includes the queue container to use a queue data structure.

• using namespace std;: Allows using names for objects and variables from the standard C++ library.

• vector<vector<int>> updateMatrix(vector<vector<int>>& mat): Defines a function updateMatrix that takes a 2D vector mat as input and returns a 2D vector.

• int m = mat.size(); and int n = mat[0].size();: Retrieves the number of rows and columns in the input matrix.

• vector<vector<int>> dist(m, vector<int>(n, INT_MAX));: Initializes a 2D vector dist with dimensions m x n and sets all values to INT_MAX.

• queue<pair<int, int>> q;: Initializes a queue of pairs to store coordinates.

• The nested loops iterate through the input matrix:

• If the current cell contains a 0, it sets the distance as 0 and pushes its coordinates onto the queue.

• vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};: Defines directions for adjacent cells (up, down, left, right).

• The while loop continues until the queue is empty:

• Pops the front element from the queue.

• Explores adjacent cells and updates their distances if a shorter path is found.

• Returns the updated distance matrix.

• int main(): Entry point of the program.

• Initializes the input matrix mat.

• Calls the updateMatrix function and stores the result in result.

• Outputs the resulting matrix result to the console.