Leetcode 542 01 Matrix

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

0 元素距离最近的0，也就是自己，所以距离还是0
1 元素就要我们求了
这很明显是图论的问题，而且是求极值，而不是判断有无解的题目，所以应当用 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];
}

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

首先找出所有 0 的节点，它们的距离是 0 ，直接更新就好了
其他的节点我们更新距离为无限远（用 INT_MAX -10000表示，减 10000 是为了防止溢出）
从 0 的位置出发，逐步更新周围的点到 0 的距离
在获得新点的时候要判断新点是否符合边界要求

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;
    }
};

可乐的博客

leetcode 542 01 Matrix

Leetcode 542 01 Matrix