这一题跟Max Area of Island 岂不是一模一样……一眼就看出来怎么做了，上代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
count += dfs(i, j, grid);
}
}
return count;
}
int dfs(int x, int y, vector<vector<char> >& grid) {
if (grid[x][y] == '0') { return 0; }
else {
grid[x][y] == '0';
if (x - 1 >= 0) { dfs(x - 1, y, grid); }
if (x + 1 < grid.size()) { dfs(x + 1, y, grid); }
if (y - 1 >= 0) { dfs(x, y - 1, grid); }
if (y + 1 < grid[x].size()) { dfs(x, y + 1, grid); }
return 1;
}
}
};
运行，怎么Stack Overflow了？来回看了几遍，感觉也不应该堆栈溢出呀……忽然一看，grid[x][y] == '0'; （笑cry.jpg)，原来是把等号写成相等判断了……改之
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
count += dfs(i, j, grid);
}
}
return count;
}
int dfs(int x, int y, vector<vector<char> >& grid) {
if (grid[x][y] == '0') { return 0; }
else {
grid[x][y] = '0';
if (x - 1 >= 0) { dfs(x - 1, y, grid); }
if (x + 1 < grid.size()) { dfs(x + 1, y, grid); }
if (y - 1 >= 0) { dfs(x, y - 1, grid); }
if (y + 1 < grid[x].size()) { dfs(x, y + 1, grid); }
return 1;
}
}
};
运行成功！结果
Runtime:16 ms, faster than 98.99% of C++ online submissions forNumber of Islands.
Memory Usage:11 MB, less than 91.19% of C++ online submissions for Number of Islands.
网友评论