【LetMeFly】542.01 矩陣

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

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

給定一個由0和1組成的矩陣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]]

提示：

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

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

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

接著在隊列不為空時，不斷出隊一個位置，并判斷這個位置的上下左右是否被遍歷過。

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

原理：

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

• 時間復雜度 O ( n m ) O(nm) O(nm)
• 空間復雜度 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)不易，轉載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128175163

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

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

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

廣告

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