【LetMeFly】542.01 矩陣

力扣題目鏈接：https://leetcode.cn/problems/01-matrix/

10多年的偏關(guān)網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整偏關(guān)建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“偏關(guān)網(wǎng)站設(shè)計(jì)”,“偏關(guān)網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

給定一個(gè)由0和1組成的矩陣mat，請輸出一個(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è)位置的上下左右是否被遍歷過。

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

原理：

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

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

AC代碼 C++

typedef pairpii;
const int direcitons[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
class Solution {public:
    vector>updateMatrix(vector>& mat) {int n = mat.size(), m = mat[0].size();
        vector>visited(n, vector(m, false));
        queueq;
        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;
    }
};

同步發(fā)文于，原創(chuàng)不易，轉(zhuǎn)載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128175163

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：LeetCode0542.01矩陣-創(chuàng)新互聯(lián)
URL地址：http://aaarwkj.com/article40/dspoeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、手機(jī)網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)