C++?LeetCode542矩陣示例詳解

更新時(shí)間：2022年12月16日 15:12:36 作者：LetMeFly

這篇文章主要為大家介紹了C++?LeetCode542矩陣示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

LeetCode 542.01 矩陣

力扣題目鏈接：leetcode.cn/problems/01…

給定一個(gè)由 0 和 1 組成的矩陣 mat ，請(qǐng)輸出一個(gè)大小相同的矩陣，其中每一個(gè)格子是 mat 中對(duì)應(yīng)位置元素到最近的 0 的距離。

兩個(gè)相鄰元素間的距離為 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]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一個(gè) 0

方法一：廣度優(yōu)先搜索

首先遍歷原始矩陣，找到所有的0，將其位置入隊(duì)。

接著在隊(duì)列不為空時(shí)，不斷出隊(duì)一個(gè)位置，并判斷這個(gè)位置的上下左右是否被遍歷過(guò)。

如果還沒(méi)有被遍歷過(guò)，那么就將新的位置入隊(duì)。并將地圖中新的位置的值修改為“出隊(duì)位置的值 + 1”

原理：

所有的原始的0最終結(jié)果都是0。廣度優(yōu)先搜索就是在所有的“0”的位置中，走一步。這一步所到的位置就是“1”步能到達(dá)的位置。同理，“1”經(jīng)過(guò)一步到達(dá)的位置就是“2”。最先到達(dá)的就是步數(shù)最少的。

時(shí)間復(fù)雜度O(nm)
空間復(fù)雜度O(nm)

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

以上就是C++ LeetCode542矩陣示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ LeetCode542矩陣的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

Qt實(shí)現(xiàn)制作簡(jiǎn)單的計(jì)算器
計(jì)算器是我們生活中很常見(jiàn)的東西，它可以由多種語(yǔ)言多種方式來(lái)實(shí)現(xiàn)。本文主要介紹的是利用Qt實(shí)現(xiàn)的簡(jiǎn)易計(jì)算器的制作，文中的示例代碼講解詳細(xì)，需要的可以參考一下
2022-12-12
C語(yǔ)言開(kāi)發(fā)簡(jiǎn)易版掃雷小游戲
本文給大家分享的是一個(gè)使用C語(yǔ)言開(kāi)發(fā)的命令行下的簡(jiǎn)易版掃雷小游戲，本身沒(méi)有什么太多的技術(shù)含量，只不過(guò)是筆者的處女作，所以還是推薦給大家，希望對(duì)大家學(xué)習(xí)C能夠有所幫助。
2015-12-12
C++實(shí)現(xiàn)簡(jiǎn)易的通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)易的通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-06-06
C++實(shí)現(xiàn)簡(jiǎn)單的信息管理系統(tǒng)
這篇文章主要為大家介紹了C++實(shí)現(xiàn)簡(jiǎn)單的信息管理系統(tǒng)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2016-04-04
分享C++三種類型new類型的運(yùn)算符使用詳情
這篇文章主要介紹了C++三種類型new運(yùn)算符的使用詳情，文章基于C++運(yùn)算展開(kāi)主題內(nèi)容，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
2022-04-04
C語(yǔ)言單鏈表遍歷與求和示例解讀
我們?cè)趯W(xué)習(xí)編程的過(guò)程中，雖然有些語(yǔ)法很簡(jiǎn)單，但是我們還是要做多題。不做題是發(fā)現(xiàn)不了問(wèn)題的，發(fā)現(xiàn)問(wèn)題我們就可以“對(duì)癥下藥”，進(jìn)行查漏補(bǔ)缺了。刷題可以先從簡(jiǎn)單題開(kāi)始刷，熟練之后再做一些可以提升自己能力的題
2022-07-07
詳解C++編程中的vector類容器用法
vector是一個(gè)標(biāo)準(zhǔn)庫(kù)中的容器,使用時(shí)需要包含#include <vector>頭文件,也可以說(shuō)vector是一個(gè)類模板而不是一種數(shù)據(jù)類型,對(duì)它的定義,需要指定類型,需要的朋友可以參考下
2016-05-05
C++基于遞歸和非遞歸算法求二叉樹(shù)鏡像的方法
這篇文章主要介紹了C++基于遞歸和非遞歸算法求二叉樹(shù)鏡像的方法,針對(duì)二叉樹(shù)遍歷結(jié)合實(shí)例形式分析了遞歸與非遞歸算法的實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下
2017-05-05
C 讀取ini文件的實(shí)例詳解
這篇文章主要介紹了C 讀取ini文件的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下
2017-10-10
C語(yǔ)言刪除輸入字符串中的空格示例代碼
最近工作中遇到了需求,要?jiǎng)h除字符串中的所有空格,就要篩選出空格字符,這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言刪除輸入字符串中的空格的相關(guān)資料,需要的朋友可以參考下
2022-12-12