給定一個包含了一些 0 和 1的非空二維數組 grid , 一個 島嶼 是由四個方向 (水準或垂直) 的 1 (代表土地) 構成的組合。你可以假設二維矩陣的四個邊緣都被水包圍着。
找到給定的二維數組中最大的島嶼面積。(如果沒有島嶼,則傳回面積為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]]
對于上面這個給定矩陣應傳回 6。注意答案不應該是11,因為島嶼隻能包含水準或垂直的四個方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
對于上面這個給定的矩陣, 傳回 0。
注意: 給定的矩陣grid 的長度和寬度都不超過 50。
每日打卡,長度和寬度不超過50,這種類型的題目做過很多次。
深度優先DFS + 回溯算法,唯一注意的地方,走過的地方置為0,
如果出現交叉點,有可能出現面積值不連續的情況,如測試例子grid2,
既向右走,又向下走,此時會出現隻能計算一個方向的面積。面積不連續
為了確定計算的面積值連續,使用引用儲存每次分叉點已計算的面積。
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int count;
count_max = 0;
vector<vector<int>> grid_temp(grid);
for (int i = 0; i < grid_temp.size(); i++) {
for (int j = 0; j < grid_temp[i].size(); j++) {
if (grid_temp[i][j] == 1) {
count = 0;
backtrace(grid_temp, i, j, count);
}
}
}
return count_max;
}
private:
int count_max;
void backtrace(vector<vector<int>>& grid_temp, int x, int y, int &count) {
if (x >= grid_temp.size() || x < 0) {
return;
}
if (y >= grid_temp[x].size() || y < 0) {
return;
}
if (grid_temp[x][y] == 0) {
return;
}
if (grid_temp[x][y] == 1) {
grid_temp[x][y] = 0;
count++;
}
if (count >= count_max) {
count_max = count;
}
backtrace(grid_temp, x + 1, y, count);
backtrace(grid_temp, x - 1, y, count);
backtrace(grid_temp, x, y + 1, count);
backtrace(grid_temp, x, y - 1, count);
}
};
int main() {
vector<vector<int>> grid1 = { {1, 1, 0, 0, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 1, 1},
{0, 0, 0, 1, 1} };
vector<vector<int>> grid2 = { {1, 1},
{1, 0} };
Solution* ps = new Solution();
cout << ps->maxAreaOfIsland(grid2) << endl;
return 0;
}