# Leetcode 542 Solution

https://leetcode.com/problems/01-matrix

## Solution

``````class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();

queue<pair<int, int>> q;

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

int filled = 0;
int total = m * n;
while (filled < total)
{
const auto& pt = q.front();
int i = pt.first >> 16;
int j = pt.first & 0x0FFFF;
int dist = pt.second;
q.pop();

if (matrix[i][j] != -1)
continue;

matrix[i][j] = dist;
filled++;

if (i > 0 && matrix[i - 1][j] == -1)
q.push(make_pair(((i - 1) << 16) + j, dist + 1));

if (i < m - 1 && matrix[i + 1][j] == -1)
q.push(make_pair(((i + 1) << 16) + j, dist + 1));

if (j > 0 && matrix[i][j - 1] == -1)
q.push(make_pair((i << 16) + j - 1, dist + 1));

if (j < n - 1 && matrix[i][j + 1] == -1)
q.push(make_pair((i << 16) + j + 1, dist + 1));
}

return matrix;
}
};
``````