亲宝软件园·资讯

展开

C++ LeetCode542矩阵示例详解

LetMeFly 人气:0

LeetCode  542.01 矩阵

力扣题目链接:leetcode.cn/problems/01…

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

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

示例 1:

输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]

示例 2:

输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]] 

提示:

方法一:广度优先搜索

首先遍历原始矩阵,找到所有的0,将其位置入队。

接着在队列不为空时,不断出队一个位置,并判断这个位置的上下左右是否被遍历过。

如果还没有被遍历过,那么就将新的位置入队。并将地图中新的位置的值修改为“出队位置的值 + 1”

原理:

所有的原始的0最终结果都是0。广度优先搜索就是在所有的“0”的位置中,走一步。这一步所到的位置就是“1”步能到达的位置。同理,“1”经过一步到达的位置就是“2”。最先到达的就是步数最少的。

AC代码

C++

typedef pair<int, int> pii;
const int direcitons[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pii> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!mat[i][j]) {
                    visited[i][j] = true;
                    q.push({i, j});
                }
            }
        }
        while (q.size()) {
            pii thisNode = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = thisNode.first + direcitons[d][0];
                int ty = thisNode.second + direcitons[d][1];
                if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                    if (!visited[tx][ty]) {
                        visited[tx][ty] = true;
                        mat[tx][ty] = mat[thisNode.first][thisNode.second] + 1;
                        q.push({tx, ty});
                    }
                }
            }
        }
        return mat;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论