200. 岛屿数量
找到一个入口,ans++,进入一个入口后,就把所有能访问的位置的is_visited都置为true
进入一个入口前,检查其合法性
class Solution {
public:
vector<vector<bool>> is_visited;
const vector<pair<int, int>> direction = {
{
0, -1}, {
1, 0}, {
-1, 0}, {
0, 1}};
int m;
int n;
bool is_valid(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
void dfs(const vector<vector<char>>& grid, int i, int j) {
is_visited[i][j] = true;
for (auto d : direction) {
int x = i + d.first;
int y = j + d.second;
if (is_valid(x, y) && !is_visited[x][y] && grid[x][y] == '1') {
dfs(grid, x, y);
}
}
}
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
is_visited.resize(m_, vector<bool>(n_, false));
int ans = 0;
for(int i = 0; i < m_; i++){
for(int j = 0; j < n_; j++){
if(!is_visited[i][j] && grid[i][j] == '1'){
// 能找到一个入口,ans++
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
};
剑指 Offer II 105. 岛屿的最大面积
访问过将is_visited置为true,从四个方向遍历后,四个方向都返回能够访问的最大面积
class Solution {
public:
vector<vector<int>> is_visited;
vector<vector<int>> direction;
int ans;
int m;
int n;
bool is_valid(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
// 返回从(init_x, init_y)出发,能走过的面积
int dfs(vector<vector<int>>& grid, int init_x, int init_y){
//if(!is_valid(init_x, init_y)) return 0;
is_visited[init_x][init_y] = true;
int cnt = 1;
for(auto d : direction){
int x = init_x + d[0];
int y = init_y + d[1];
if(is_valid(x, y) && !is_visited[x][y] && grid[x][y] == 1) {
cnt += dfs(grid, x, y);
}
}
// 从一个入口的四个方向访问完后,用当前岛屿面积更新ans
ans = max(ans, cnt);
return cnt;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
ans = 0;
is_visited.resize(m, vector<int>(n, false));
direction = {
{
0,1},{
1,0},{
0,-1},{
-1,0}};
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(!is_visited[i][j] && grid[i][j] == 1) dfs(grid, i, j);
}
}
return ans;
}
};
文章评论