BFS解決FloodFill算法

1.圖像渲染

733. 圖像渲染 - 力扣（LeetCode）

1.題目解析

有一幅以?m x n?的二維整數數組表示的圖畫?image?，其中?image[i][j]?表示該圖畫的像素值大小。你也被給予三個整數?sr?,??sc?和?color?。你應該從像素?image[sr][sc]?開始對圖像進行上色?填充?。

為了完成?上色工作：

  1. 從初始像素開始，將其顏色改為?color。
  2. 對初始坐標的?上下左右四個方向上?相鄰且與初始像素的原始顏色同色的像素點執行相同操作。
  3. 通過檢查與初始像素的原始顏色相同的相鄰像素并修改其顏色來繼續?重復?此過程。
  4. 當?沒有?其它原始顏色的相鄰像素時?停止?操作。

最后返回經過上色渲染?修改?后的圖像?。

2.示例

示例 1:

輸入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, color = 2

輸出：[[2,2,2],[2,2,0],[2,0,1]]

解釋：在圖像的正中間，坐標?(sr,sc)=(1,1)?（即紅色像素）,在路徑上所有符合條件的像素點的顏色都被更改成相同的新顏色（即藍色像素）。

注意，右下角的像素?沒有?更改為2，因為它不是在上下左右四個方向上與初始點相連的像素點。

3.解題思路

------本題使用的方法BFS,還有方向坐標int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};

  1. 參數：

    • color：新填充顏色，用于替換與起始點顏色不同的區域。

    • sr 和 sc：起始點的行和列索引。

    • image：輸入圖像，是一個二維整數矩陣，其中每個元素表示像素值。

  2. 檢查起始點顏色是否與新顏色相同，如果相同，直接返回原始圖像。

  3. 獲取圖像的行數 m 和列數 n。

  4. 初始化一個隊列 q，將起始點 (sr, sc) 入隊。

  5. 當隊列不為空時，執行 BFS 遍歷：

    • 彈出隊列頭部的點，獲取當前點的坐標 (a, b)。

    • 檢查當前點的顏色，如果已經是新顏色，跳過。

    • 將新顏色賦值給當前點。

    • 遍歷當前點的四個方向，如果相鄰點在圖像范圍內且顏色與起始點相同，將其加入隊列。

4.代碼實現

class Solution {typedef pair<int , int> PII;//定義方向變量int dx[4] = {0 , 0 , 1 , -1};int dy[4] = {1 , -1 , 0 , 0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int prev = image[sr][sc];if(prev == color) return image;int m = image.size(), n = image[0].size();queue<PII> q;q.push({sr , sc});while(! q.empty()){auto [a , b] = q.front();image [a][b] = color;q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev )q.push({x , y});}} return image;}
};

2.島嶼數量

200. 島嶼數量 - 力扣（LeetCode）

1.題目解析

給你一個由?'1'（陸地）和?'0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

2.示例

示例 1：

輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
輸出：1

示例 2：

輸入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
輸出：3

3.解題思路

遍歷整個矩陣，每次找到「?塊陸地」的時候：

? 說明找到「?個島嶼」，記錄到最終結果 ret ??；

? 并且將這個陸地相連的所有陸地，也就是這塊「島嶼」，全部「變成海洋」。這樣的話，我們下次 遍歷到這塊島嶼的時候，它「已經是海洋」了，不會影響最終結果。

? 其中「變成海洋」的操作，可以利?「深搜」和「寬搜」解決，其實就是733.圖像渲染這道題~

  1. bfs 方法：

    • 使用 queue 實現廣度優先搜索。

    • 將起始點 (i, j) 入隊，并標記為已訪問。

    • 當隊列不為空時，循環處理隊列中的點。

    • 對于每個點，檢查四個方向的相鄰單元格。

    • 如果相鄰單元格在網格范圍內、未訪問過、且值為 '1'，則將其加入隊列，并標記為已訪問。

  2. numIslands 方法：

    • 初始化島嶼數量 ret 為 0。

    • 遍歷網格的每個單元格，對于值為 '1' 的單元格，如果未訪問過，則調用 bfs 方法進行搜索，并增加島嶼計數。

    • 返回計算得到的島嶼數量。

4.代碼實現

class Solution {int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool visi[301][301];public:void bfs(vector<vector<char>>& grid , int i, int j){queue<pair<int , int>> q;q.push({i , j});visi[i][j] = true;while(q.size()){auto [a , b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !visi[x][y] && grid[x][y] == '1'){q.push({x , y});visi[x][y] = true;}}}}int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(grid[i][j] == '1' && !visi[i][j]){ret++;bfs(grid, i ,j);}}return ret;}
};

?3.島嶼的最大面積

1.題目解析

給你一個大小為?m x n?的二進制矩陣?grid?。

島嶼?是由一些相鄰的?1?(代表土地) 構成的組合，這里的「相鄰」要求兩個?1?必須在?水平或者豎直的四個方向上?相鄰。你可以假設?grid?的四個邊緣都被?0（代表水）包圍著。

島嶼的面積是島上值為?1?的單元格的數目。

計算并返回?grid?中最大的島嶼面積。如果沒有島嶼，則返回面積為?0?。

2.示例

示例 1：

輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應該是 11，因為島嶼只能包含水平或垂直這四個方向上的 1

示例 2：

輸入：grid = [[0,0,0,0,0,0,0,0]]
輸出：0

3.解題思路

1.與第二道例題島嶼數量類似，只需定義一個計數器，來計算個數。

2.注意方向變量（dx、dy）的使用

3.還要讓visi進行賦值

4.代碼實現

class Solution {int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool visi[51][51];
public:int bfs(vector<vector<int>>& grid, int i, int j){queue<pair<int , int>> q;int count = 0;q.push({i , j});visi[i][j] = true;count++;while(q.size()){auto [a , b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !visi[x][y]){q.push({x , y});visi[x][y] = true;count++;}} }return count;}int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(grid[i][j] == 1 && !visi[i][j]){ret = max(ret , bfs(grid , i, j));}}return ret;}
};

4.被圍繞的區域

130. 被圍繞的區域 - 力扣（LeetCode）

1.題目解析

給你一個?m x n?的矩陣?board?，由若干字符?'X'?和?'O'?組成，捕獲?所有?被圍繞的區域：

  • 連接：一個單元格與水平或垂直方向上相鄰的單元格連接。
  • 區域：連接所有?'O'?的單元格來形成一個區域。
  • 圍繞：如果您可以用?'X'?單元格?連接這個區域，并且區域中沒有任何單元格位于?board?邊緣，則該區域被?'X'?單元格圍繞。

通過?原地?將輸入矩陣中的所有?'O'?替換為?'X'?來?捕獲被圍繞的區域。你不需要返回任何值。

2.示例

示例 1：

輸入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

輸出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解釋：

在上圖中，底部的區域沒有被捕獲，因為它在 board 的邊緣并且不能被圍繞。

示例 2：

輸入：board = [["X"]]

輸出：[["X"]]

3.解題思路

正難則反。 可以先利? bfs 將與邊緣相連的 '0' 區域做上標記，然后重新遍歷矩陣，將沒有標記過的 '0' 修改成 'X' 即可。

4.代碼實現

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;
public:void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int, int>> q;q.push({i, j});board[i][j] = '.';while(q.size()){auto [a, b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){q.push({x, y});board[x][y] = '.';}}}}void solve(vector<vector<char>>& board) {//將靠近邊上的字符'O'轉換成字符‘.’m = board.size(), n = board[0].size();for(int j = 0; j < n; j++){if(board[0][j] == 'O') bfs(board, 0, j);if(board[m - 1][j] == 'O') bfs(board, m - 1, j);}for(int i = 0; i < m; i++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n - 1] == 'O') bfs(board, i, n - 1);}//還原for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O') board[i][j] = 'X';else if(board[i][j] == '.') board[i][j] = 'O';}}}
};

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/898997.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/898997.shtml
英文地址，請注明出處：http://en.pswp.cn/news/898997.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

LeetCode(977)：有序數組的平方

LeetCode(977)：有序數組的平方

有序數組的平方 題目鏈接 題目&#xff1a;給你一個按非遞減順序排序的整數數組 nums&#xff0c;返回每個數字的平方組成的新數組&#xff0c;要求也按非遞減順序排序。 //暴力 #include<stdio.h> void sort(int *nums,int n){for(int i0;i<n;i)for(int ji1;j<…
閱讀更多...
OpenAI的“噩夢”，DeepSeek V3-0324效率革命展現中國AI雄心

OpenAI的“噩夢”，DeepSeek V3-0324效率革命展現中國AI雄心

3月24日晚&#xff0c;DeepSeek低調發布其V3模型的小版本更新——DeepSeek V3-0324&#xff0c;這一操作立即在社區引發熱議。據悉&#xff0c;該版本已集成至DeepSeek官網、應用程序和小程序&#xff0c;用戶只需關閉“Deep Thinking”功能即可體驗。另該模型已在Hugging Face…
閱讀更多...
mysql創建庫表插入數據演示

mysql創建庫表插入數據演示

show databases; use zzj; create table stu (sid int primary key,name varchar(10) not null,sex varchar(2) );desc stu;insert into stu (sid, name, sex) values (1, zzj, 男);select * from stu; desc stu: select * from stu:
閱讀更多...
C語言 - 整數與浮點數運算的類型轉換規則

C語言 - 整數與浮點數運算的類型轉換規則

C 語言整數與浮點數運算的類型轉換規則 在 C 語言中&#xff0c;不同數據類型在運算時會進行 隱式類型轉換。當 有符號整數&#xff08;int&#xff09;、無符號整數&#xff08;unsigned int&#xff09; 和 浮點型&#xff08;float、double&#xff09; 進行運算時&#xf…
閱讀更多...
用SVG繞過瀏覽器XSS審計

用SVG繞過瀏覽器XSS審計

[Translated From]&#xff1a;http://insert-script.blogspot.com/2014/02/svg-fun-time-firefox-svg-vector.html SVG - <use> element SVG中的<use>元素用于重用其他元素&#xff0c;主要用于聯接<defs>和alike&#xff0c;而我們卻用它來引用外部SVG文件…
閱讀更多...
【構建CV圖像識別系統】從傳統方法到深度學習

【構建CV圖像識別系統】從傳統方法到深度學習

目錄 1. 圖像的基本概念1.1 像素與色彩1.2 過濾與卷積 2. 圖像分類與檢測3. 圖像特征的提取3.1 全局特征3.2 局部特征3.2.1 邊緣&#xff08;Edge&#xff09;3.2.2 角點&#xff08;Corner&#xff09;3.2.3 SIFT 特征 4. 傳統方法與深度學習在圖像識別中的應用4.1 基于傳統方…
閱讀更多...
Kubernetes高級應用之-重啟策略

Kubernetes高級應用之-重啟策略

一、介紹&#xff0b;擴展應用&#xff08;涉及的高級資源在后續會寫出來&#xff09; # Kubernetes Pod重啟策略&#xff08;RestartPolicy&#xff09;全面解析 ## 一、重啟策略的核心價值與重要性 在Kubernetes集群中&#xff0c;Pod重啟策略&#xff08;RestartPolicy&a…
閱讀更多...
簡記_單片機硬件最小系統設計

簡記_單片機硬件最小系統設計

以STM32為例&#xff1a; 一、電源 1.1、數字電源 IO電源&#xff1a;VDD、VSS&#xff1a;1.8~3.6V&#xff0c;常用3.3V&#xff0c;去耦電容1 x 10u N x 100n &#xff1b; 內核電源&#xff1a;內嵌的穩壓器輸出&#xff1a;1.2V&#xff0c;給內核、存儲器、數字外設…
閱讀更多...
matlab使用fmincon開加速

matlab使用fmincon開加速

在使用 fmincon 進行優化時&#xff0c;可以通過以下方法加速優化過程。這些方法主要涉及算法選擇、并行計算、減少函數調用次數等。以下是具體建議和實現方式&#xff1a; 1. 選擇合適的優化算法 fmincon 支持多種優化算法&#xff0c;不同的算法適用于不同類型的優化問題。選…
閱讀更多...
MySQL顛覆版系列————MySQL新特性（開啟數據庫的新紀元）下篇

MySQL顛覆版系列————MySQL新特性（開啟數據庫的新紀元）下篇

文章目錄 前言五、持久化全局變量5.1 持久化全局變量特點5.2 持久化全局變量實例5.3 持久化全局變量注意事項 六、降序索引&#xff08;Descending Indexes&#xff09;6.1 降序索引&#xff08;Descending Indexes&#xff09;特點6.2 降序索引&#xff08;Descending Indexes…
閱讀更多...
解析1688.item_search_shop接口：獲取店鋪所有商品返回數據詳細說明

解析1688.item_search_shop接口：獲取店鋪所有商品返回數據詳細說明

一、引言 在電商領域&#xff0c;獲取特定店鋪的所有商品信息是運營分析、市場調研和自動化處理的重要基礎。1688作為國內領先的B2B電商平臺&#xff0c;提供了豐富的API接口供開發者使用。其中&#xff0c;item_search_shop接口允許開發者通過店鋪ID獲取該店鋪的所有商品信息…
閱讀更多...
新書速覽|OpenCV計算機視覺開發實踐:基于Python

新書速覽|OpenCV計算機視覺開發實踐:基于Python

《OpenCV計算機視覺開發實踐:基于Python》 本書內容 OpenCV是一個跨平臺計算機視覺和機器學習軟件庫&#xff0c;也是計算機視覺領域的開發人員必須掌握的技術。《OpenCV計算機視覺開發實踐:基于Python》基于Python 3.8全面系統地介紹OpenCV 4.10的使用&#xff0c;并配套示例…
閱讀更多...
微服務架構中的服務發現與 Consul 實踐

微服務架構中的服務發現與 Consul 實踐

在微服務架構中&#xff0c;服務之間的通信是核心問題之一。隨著服務數量的增長&#xff0c;如何高效地管理和定位服務實例變得尤為重要。本文將介紹服務發現的基本概念&#xff0c;并詳細講解如何使用 Consul 進行服務注冊、發現和健康檢查。 1. 什么是服務發現&#xff1f; …
閱讀更多...
PyTorch 深度學習實戰（24）：分層強化學習（HRL）

PyTorch 深度學習實戰（24）：分層強化學習（HRL）

一、分層強化學習原理 1. 分層學習核心思想 分層強化學習&#xff08;Hierarchical Reinforcement Learning, HRL&#xff09;通過時間抽象和任務分解解決復雜長程任務。核心思想是&#xff1a; 對比維度傳統強化學習分層強化學習策略結構單一策略直接輸出動作高層策略選擇選…
閱讀更多...
車載網絡測試實操源碼_使用CAPL腳本進行UDS刷寫及其自動化測試

車載網絡測試實操源碼_使用CAPL腳本進行UDS刷寫及其自動化測試

系列文章目錄 使用CAPL腳本解析hex、S19、vbf文件 使用CAPL腳本對CAN報文的Counter、CRC、周期、錯誤幀進行實時監控 使用CAPL腳本模擬發送符合協議要求(Counter和CRC)的CAN報文 使用CAPL腳本控制繼電器實現CAN線、電源線的通斷 使用CAPL腳本實現安全訪問解鎖 使用CAPL腳本實現…
閱讀更多...
Spring Boot整合Spring Data JPA

Spring Boot整合Spring Data JPA

Spring Data作為Spring全家桶中重要的一員&#xff0c;在Spring項目全球使用市場份額排名中多次居前位&#xff0c;而在Spring Data子項目的使用份額排名中&#xff0c;Spring Data JPA也一直名列前茅。Spring Boot為Spring Data JPA提供了啟動器&#xff0c;使Spring Data JPA…
閱讀更多...
JS 應用WebPack 打包器第三方庫 JQuery安裝使用安全檢測

JS 應用WebPack 打包器第三方庫 JQuery安裝使用安全檢測

# 打包器 -WebPack- 使用 & 安全 參考&#xff1a; https://mp.weixin.qq.com/s/J3bpy-SsCnQ1lBov1L98WA Webpack 是一個模塊打包器。在 Webpack 中會將前端的所有資源文件都作為模塊處理。 它將根據模塊的依賴關系進行分析&#xff0c;生成對應的資源。 五個核心概…
閱讀更多...
Oracle歸檔配置及檢查

Oracle歸檔配置及檢查

配置歸檔位置到 USE_DB_RECOVERY_FILE_DEST&#xff0c;并設置存儲大小 startup mount; !mkdir /db/archivelog ALTER SYSTEM SET db_recovery_file_dest_size100G SCOPEBOTH; ALTER SYSTEM SET db_recovery_file_dest/db/archivelog SCOPEBOTH; ALTER SYSTEM SET log_archive…
閱讀更多...
Four.meme是什么，一篇文章讀懂

Four.meme是什么，一篇文章讀懂

一、什么是Four.meme&#xff1f; Four.meme 是一個運行在 BNB 鏈的去中心化平臺旨在為 meme 代幣供公平啟動服務。它允許用戶以極低的成本創建和推出 meme 代幣&#xff0c;無需預售或團隊分配&#xff0c;它消除了傳統的預售、種子輪和團隊分配&#xff0c;確保所有參與者有…
閱讀更多...
Simula語言的正則表達式

Simula語言的正則表達式

Simula語言中的正則表達式 引言 Simula是一種開創性的編程語言&#xff0c;最初在1960年代由Ole-Johan Dahl和Kristen Nygaard在挪威的計算機中心開發。它不僅是面向對象編程的先驅&#xff0c;還在模擬和各種計算領域有顯著的應用。然而&#xff0c;Simula語言本身并不直接支…
閱讀更多...
最新文章

Copyright @ 2022~2023