leetcode 542 01 Matrix

Posted by kele on April 5, 2019

Leetcode 542 01 Matrix

给定一个矩阵,求矩阵中的元素到相邻的最近的0的距离是多少,返回结果矩阵

  1. 0 元素距离最近的0,也就是自己,所以距离还是0
  2. 1 元素就要我们求了
  3. 这很明显是图论的问题,而且是求极值,而不是判断有无解的题目,所以应当用 BFS,广度优先搜索

比较巧妙的地方在于构造移动方向,以前见过的迷宫问题的移动方向是通过两个数组,一个控制 x 方向,另一个控制 y 方向,然后通过二重循环,遍历四个方向 :

int x_dir[]={0,0,1,-1};
int y_dir[]={1,-1,0,0};

for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
        int new_x=cur_x+x_dir[i];
        int new_y=cur_y+y_dir[j];
    }
}

看到 solution 中构造的要更简洁一些:

int dict[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
for(int i=0;i<4;i++){
    int new_x=cur_x+dict[i][0];
    int new_y=cur_y+dict[i][1];
}

既然是广度优先搜索,所以我们要尽可能地搜索所有节点,所以我们需要一个队列容器来存储要访问的节点:

  1. 首先找出所有 0 的节点,它们的距离是 0 ,直接更新就好了
  2. 其他的节点我们更新距离为无限远(用 INT_MAX -10000表示,减 10000 是为了防止溢出)
  3. 从 0 的位置出发,逐步更新周围的点到 0 的距离
  4. 在获得新点的时候要判断新点是否符合边界要求
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row=matrix.size();
        if(row<=0) return matrix;
        int col=matrix[0].size();
        vector<vector<int>> res(row,vector<int>(col,INT_MAX-10000));
        queue<pair<int,int>> qq;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j]==0){
                    res[i][j]=0;
                    qq.push({i,j});
                }
            }
        }
        int dict[4][2]={ {0,1},{1,0},{-1,0},{0,-1} };
        while(!qq.empty()){
            pair<int,int> pp=qq.front();
            qq.pop();
            for(int i=0;i<4;i++){
                int new_x=pp.first+dict[i][0];
                int new_y=pp.second+dict[i][1];
                if(new_x>=0&&new_y>=0&&new_x<row&&new_y<col){
                    if(res[new_x][new_y]>res[pp.first][pp.second]+1){
                        res[new_x][new_y]=res[pp.first][pp.second]+1;
                        qq.push({new_x,new_y});
                    }
                }
            }
        }
        return res;
    }
};