岛屿数量
目标在边界上
class Solution {
public:
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<char>> g;
void dfs(int x, int y) {
g[x][y] = 0;
for(int i=0; i<4; ++i) {
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1') {
dfs(a, b);
}
}
}
int numIslands(vector<vector<char>>& grid) {
g = grid;
int ret = 0;
for(int i=0; i<g.size(); ++i) {
for(int j=0; j<g[i].size(); ++j) {
if(g[i][j] == '1'){
dfs(i, j);
ret++;
}
}
}
return ret;
}
};
统计封闭岛屿的数目
目标被边界包围
class Solution {
public:
int n, m;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int dfs(int x, int y, vector<vector<int>>& g) {
int ret = 1;
g[x][y] = 1;
for(int i=0; i<4; ++i) {
int xx = x + dx[i], yy = y + dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) {
ret = 0;
continue;
}
if(!g[xx][yy] && !dfs(xx, yy, g)) ret = 0; // 不合法
}
return ret;
}
int closedIsland(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
int ret = 0;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
if(grid[i][j] == 0) ret += dfs(i, j, grid);
}
}
return ret;
}
};