542.01 Matrix

如果不是0, 那麼到0的最近距離是多少,

首先, 我們先將所有是0的位置, 加到一個queue, 不是的直接設INT_MAX, 接著我們取出這些0, 倘若他的四周有直的距離太大, 因為本身是0, 一定能感化他, 所以它變成1了, 並把他加到queue中, 說不定他能在感化更多人

那如果他的四周, 發現直比自己小, 或是是無效的(在邊界的話), 我們就跳過, 不要浪費時間了

這想法真的蠻猛的

class Solution {
public:
  vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
      queue<pair<int, int>> q;
      int m = matrix.size();
      int n = matrix[0].size();
      vector<vector<int>> dirs = {{0,-1},{-1,0},{0,1},{1,0}};
for(int i = 0; i < m; i++){
          for(int j = 0; j< n; j++){
              if(matrix[i][j] == 0){
                  q.push({i, j});
              }else{
                  matrix[i][j] = INT_MAX;
              }
          }
      }
      while(!q.empty()){
          pair<int, int> cur = q.front();
          q.pop();
          for(auto cord: dirs){
              int x = cur.first + cord[0];
              int y = cur.second + cord[1];
              if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[cur.first][cur.second] + 1){
                  continue;
              }
              matrix[x][y] = matrix[cur.first][cur.second] + 1;
              q.push({x, y});
          }
      }
      return matrix;
  }
};