文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 BFS廣度優(yōu)先搜索
    • 2.2 DFS深度優(yōu)先搜索

1. 題目

給定一個(gè)包含了一些 0 和 1的非空二維數(shù)組 grid , 一個(gè) 島嶼 是由四個(gè)方向 (水平或垂直) 的 1 (代表土地) 構(gòu)成的組合。你可以假設(shè)二維矩陣的四個(gè)邊緣都被水包圍著。

找到給定的二維數(shù)組中最大的島嶼面積。(如果沒(méi)有島嶼，則返回面積為0。)

示例 1: [[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]] 對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是11，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的‘1’。示例 2: [[0,0,0,0,0,0,0,0]] 對(duì)于上面這個(gè)給定的矩陣, 返回 0。 注意: 給定的矩陣grid 的長(zhǎng)度和寬度都不超過(guò) 50。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/max-area-of-island
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 簡(jiǎn)單的題目
• 圖的廣度或者深度優(yōu)先搜索
• visited數(shù)組訪問(wèn)標(biāo)記—> 直接在地圖上改數(shù)據(jù)為0

2.1 BFS廣度優(yōu)先搜索

class Solution {int maxS = 0;int m, n;vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}}; public:int maxAreaOfIsland(vector<vector<int>>& grid) {int curS = 0, i, j, i0, j0, k, x, y;m = grid.size(), n = grid[0].size();queue<pair<int,int>> q;for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(grid[i][j])// == 1{q.push({i,j});curS = 1;//當(dāng)前面積為1grid[i][j] = 0;//訪問(wèn)過(guò)了while(!q.empty()){i0 = q.front().first;j0 = q.front().second;q.pop();for(k = 0; k < 4; ++k){x = i0+dir[k][0];y = j0+dir[k][1];if(x>=0 && x<m && y>=0 && y<n && grid[x][y]){q.push({x,y});grid[x][y] = 0;//訪問(wèn)過(guò)了curS++;}}}if(curS > maxS)maxS = curS;}}}return maxS;} };

2.2 DFS深度優(yōu)先搜索

class Solution {int maxS = 0;int m, n;vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}}; public:int maxAreaOfIsland(vector<vector<int>>& grid) {int curS = 0, i, j;m = grid.size(), n = grid[0].size();for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(grid[i][j])// == 1{curS = 1;//當(dāng)前面積為1grid[i][j] = 0;//訪問(wèn)過(guò)了dfs(grid,i,j,curS);if(curS > maxS)maxS = curS;}}}return maxS;}void dfs(vector<vector<int>>& grid, int i, int j, int &curS){int x, y, k;for(k = 0; k < 4; ++k){x = i+dir[k][0];y = j+dir[k][1];if(x>=0 && x<m && y>=0 && y<n && grid[x][y]){grid[x][y] = 0;//訪問(wèn)過(guò)了curS++;dfs(grid,x,y,curS);}}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 695. 岛屿的最大面积（图的BFS/DFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。