Matrix Distance Nearest 0

PROBLEM

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example1

*Input*: mat = [[0,0,0],[0,1,0],[0,0,0]]
*Output*: [[0,0,0],[0,1,0],[0,0,0]]

Example2

*Input*: mat = [[0,0,0],[0,1,0],[1,1,1]]
*Output*: [[0,0,0],[0,1,0],[1,2,1]]

SOLVING

we’ll use Breadth-first Search method

Steps

  • Create matrix result with the same size filled by 0
  • Create a queue
  • Parcor the list if there is a 1 next to a 0 :
    • Add in result 1 at it’s position (because it’s at one cell from a zero)
    • And push to the queue it’s position
  • While queue not empty:
    • Pop the queu to get the current value
    • Check the neighboors (up, down, right, left)
    • If it’s equal to 1 and equal to 0 in result (That means we didn’t see this cell before):
      • Push to the queue it’s position
      • Add in result the parent value in result + 1
  • Return result

Code

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

    for (int r = 0; r < m; r++) {
      for (int c = 0; c < n; c++) {
	if (mat[r][c] == 0)
	  continue;
	if (nextToZero(mat, r, c)) {
	  q.push({r, c});
	  result[r][c] = 1;
	}
      }
    }

    while (!q.empty()) {
      pair<int, int> current = q.front();
      q.pop();

      for (int indexNext = 0; indexNext < 4; indexNext++) {
	int newR = current.first + distR[indexNext];
	int newC = current.second + distC[indexNext];

	if (newR < 0 || newR >= m || newC < 0 || newC >= n)
	  continue;
	if (mat[newR][newC] == 1 && result[newR][newC] == 0) {
	  q.push({newR, newC});
	  result[newR][newC] = result[current.first][current.second] + 1;
	}
      }
    }

    return result;
  }

private:
  int m;
  int n;
  queue<pair<int, int>> q;
  const int distC[4] = {0, 0, -1, 1};
  const int distR[4] = {-1, 1, 0, 0};

  bool nextToZero(vector<vector<int>> &mat, int r, int c) {
    for (int indexNext = 0; indexNext < 4; indexNext++) {
      int newR = r + distR[indexNext];
      int newC = c + distC[indexNext];

      if (newR < 0 || newR >= m || newC < 0 || newC >= n ||
	  mat[newR][newC] != 0)
	continue;
      return true;
    }

    return false;
  }
};