描述

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

DFS

复杂度接近O(m2n2） 

  1. class Solution {
  2. public:
  3.     int dir[5] = {-1, 0, 1, 0, -1};
  4.     vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
  5.         int n = mat.size();
  6.         int m = mat[0].size();
  7.         vector<vector<int>> res(n, vector<int>(m, INT_MAX));
  8.         for (int i = 0; i < n; ++i)
  9.         {
  10.             for (int j = 0; j < m; ++j)
  11.             {
  12.                 if (mat[i][j] == 0)
  13.                 {
  14.                     dfs(mat, res, i, j, 0);
  15.                 }
  16.             }
  17.         }
  19.         return res;
  20.     }
  21.     void dfs(vector<vector<int>>& mat, vector<vector<int>>& res, int i, int j, int dist)
  22.     {
  23.         int n = mat.size();
  24.         int m = mat[0].size();
  25.         if (i >= n || i < 0) return;
  26.         if (j >= m || j < 0) return;
  28.         if (mat[i][j] == 0 && dist > 0) return;
  30.         if (res[i][j] <= dist) return;
  32.         res[i][j] = dist;
  34.         for (int k = 0; k < 4; ++k)
  35.         {
  36.             dfs(mat, res, i+dir[k], j+dir[k+1], dist+1);
  37.         }
  38.     }
  39. };

BFS