class Solution

{

public:

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

  {

    if (matrix.size() ==  || matrix[].size() == )

      return matrix;

    int n;

    int m;

    n = matrix.size();

    m = matrix[].size();

    int rangeNum = n + m;

    vector<vector<int>> dis(n, vector<int>(m, ));

    for (int i = ; i < n; i++)

      for (int j = ; j < m; j++)

      {

        if (matrix[i][j] == )

          dis[i][j] = ;

        else

        {

          int up = (i > ) ? dis[i - ][j] : rangeNum;

          int left = (j > ) ? dis[i][j - ] : rangeNum;

          dis[i][j] = min(left, up) + ;

        }

      }

    for (int i = n - ; i >= ; i--)

      for (int j = m - ; j >= ; j--)

      {

        if (matrix[i][j] == )

          dis[i][j] = ;

        else

        {

          int right = (j + ) < m ? dis[i][j + ] : rangeNum;

          int down = (i + ) < n ? dis[i + ][j] : rangeNum;

          dis[i][j] = min(min(right, down) + , dis[i][j]);

        }

      }

    return dis;

  }

};

class Solution

{

private:

  bool isValid(int m, int n, int x, int y)

  {

    return x >=  && y >=  && x < m && y < n;

  }

  int getShortestDistance(int m, int n, int x, int y, vector<vector<int>> &distance)

  {

    int result = distance[x][y];

    if (isValid(m, n, x, y + ) && distance[x][y + ] != INT_MAX)

    {

      result = min(result,  + distance[x][y + ]);

    }

    if (isValid(m, n, x, y - ) && distance[x][y - ] != INT_MAX)

    {

      result = min(result,  + distance[x][y - ]);

    }

    if (isValid(m, n, x + , y) && distance[x + ][y] != INT_MAX)

    {

      result = min(result,  + distance[x + ][y]);

    }

    if (isValid(m, n, x - , y) && distance[x - ][y] != INT_MAX)

    {

      result = min(result,  + distance[x - ][y]);

    }

    return result;

  }

public:

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

  {

    int m = matrix.size();

    int n = matrix[].size();

    vector<vector<int>> distance(m, vector<int>(n, INT_MAX));

    queue<pair<int, int>> visit;

    for (int i = ; i < m; i++)

    {

      for (int j = ; j < n; j++)

      {

        if (matrix[i][j] == )

        {

          distance[i][j] = ;

          visit.push(make_pair(i, j + ));

          visit.push(make_pair(i, j - ));

          visit.push(make_pair(i + , j));

          visit.push(make_pair(i - , j));

        }

      }

    }

    while (!visit.empty())

    {

      pair<int, int> cur = visit.front();

      visit.pop();

      int x = cur.first;

      int y = cur.second;

      if (isValid(m, n, x, y))

      {

        int shortestD = getShortestDistance(m, n, x, y, distance);

        if (shortestD < distance[x][y])

        {

          distance[x][y] = shortestD;

          visit.push(make_pair(x, y + ));

          visit.push(make_pair(x, y - ));

          visit.push(make_pair(x + , y));

          visit.push(make_pair(x - , y));

        }

      }

    }

    return distance;

  }

};