在DFS这一块一直是比较弱的，因此就去看了DFS相关的一些题目，并找到了岛屿的一系列问题。
图类DFS方法
图通常是由方格组成，通过方格中的元素来对图的DFS进行限制。岛屿问题便是其中经典的一类。在岛屿问题中，通常由$1$表示陆地，由$2$表示海洋，当每个方格都相邻时，组成的一个全$1$方格域即为一个岛屿。（这里不包含对角相邻）
DFS框架
DFS也是一种意义上的递归，因此在一个DFS程序中首先要做的便是设定递归出口。类似于树结构可以利用指针为空等条件，在岛屿问题中，我们需要判断边界，也需要判断当前方格是否是陆地。因此在递归出口设置中就需要两个条件进行限制。
之后DFS就要考虑下一步搜索与前一轮搜索之间的区别。岛屿问题中最主要的区别便是遍历方格的四个邻格，其余的区别便需要依题目而定。因此我们可以得到以下的岛屿类问题的DFS框架
class Solution {
private:
bool inRange(vector<vector<int>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
void dfs(vector<vector<int>>& grid, int pos_x, int pos_y) {
if (!inRange(grid, pos_x, pos_y)) return;
if (grid[pos_x][pos_y] != 1) return;
dfs(grid, pos_x - 1, pos_y);
dfs(grid, pos_x + 1, pos_y);
dfs(grid, pos_x, pos_y + 1);
dfs(grid, pos_x, pos_y - 1);
}
}
避免重复遍历
在DFS中一个重要的问题就是要避免重复遍历，不然可能会造成程序原地打转的现象。在岛屿一类的问题中，可以将已经遍历过的方块修改其元素为$0$或者为非题中给出元素。因此我们可以修改上述的DFS模板如下
class Solution {
private:
bool inRange(vector<vector<int>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
void dfs(vector<vector<int>>& grid, int pos_x, int pos_y) {
if (!inRange(grid, pos_x, pos_y)) return;
if (grid[pos_x][pos_y] != 1) return;
grid[pos_x][pos_y] = 2;
dfs(grid, pos_x - 1, pos_y);
dfs(grid, pos_x + 1, pos_y);
dfs(grid, pos_x, pos_y + 1);
dfs(grid, pos_x, pos_y - 1);
}
};
岛屿问题解法
岛屿数量问题
其实粗看题目，很容易能想到并查集能够解决这类问题，但是DFS应该较为常见的解法，这道题也是最为简单的DFS。
我们可以这么想，当你使用DFS时，每次遍历到的都是相邻的方格，因此在一次DFS过程中，遍历过的所有陆地应该是属于同一块岛屿的，而在遍历的过程中我们应当将已走过的陆地更改为不可走。这样一来就会使之前的岛屿失效。
那么如何寻找下一个岛屿呢？答案也就是寻找下一个在地图中尚未使用过的$1$，之后在对这个$1$进行DFS，也就可以得到另一个岛屿了。
因此要想获得岛屿的数量，其实就是在整个地图执行DFS算法的次数。
class Solution {
private:
bool inRange(vector<vector<char>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
void dfs(vector<vector<char>>& grid, int pos_x, int pos_y) {
if (!inRange(grid, pos_x, pos_y)) return;
if (grid[pos_x][pos_y] != '1') return;
grid[pos_x][pos_y] = '2';
dfs(grid, pos_x - 1, pos_y);
dfs(grid, pos_x + 1, pos_y);
dfs(grid, pos_x, pos_y + 1);
dfs(grid, pos_x, pos_y - 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int row = grid.size();
int col = grid[0].size();
int res = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == '1') {
++res;
dfs(grid, i, j);
}
}
}
return res;
}
};
岛屿的最大面积
这个问题和上一个问题其实本质上没什么区别，你都需要在整个地图中去遍历出所有的岛屿，无非需要的就是在DFS的过程中，你需要统计已走过的陆地数量。当遍历完所有的岛屿之后，取这些值中的最大值即可。
因此在这个问题中，我们只需要在每次进入DFS函数中，如果走过的是陆地，那么就对其面积（area）$+1$即可。（使用C++时，可以传递引用避免无法改变形参的问题）。
class Solution {
private:
bool inRange(vector<vector<int>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
void dfs(vector<vector<int>>& grid, int pos_x, int pos_y, int& area) {
if (!inRange(grid, pos_x, pos_y)) return;
if (grid[pos_x][pos_y] != 1) return;
++area;
grid[pos_x][pos_y] = 2;
dfs(grid, pos_x - 1, pos_y, area);
dfs(grid, pos_x + 1, pos_y, area);
dfs(grid, pos_x, pos_y + 1, area);
dfs(grid, pos_x, pos_y - 1, area);
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
int res = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == 1) {
int area = 0;
dfs(grid, i, j, area);
res = max(res, area);
}
}
}
return res;
}
};
岛屿的周长
这道题要求的是岛屿的周长，这道题最终是在题解的启发下才做出来的。
对于一张地图，如果我们遍历到一个海洋结点（$0$），这时候表明岛屿有一条边与其相接，而当我们遍历出地图时，也表明有一条边与岛屿相接，相反，如果是陆地，则对岛屿的周长没有影响。
所以我们只需要在DFS中分以上三种情况进行讨论，将最后的结果相加即可得到岛屿的周长。
class Solution {
private:
bool inRange(vector<vector<int>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
int dfs(vector<vector<int>>& grid, int pos_x, int pos_y) {
if (!inRange(grid, pos_x, pos_y)) return 1;
if (grid[pos_x][pos_y] == 0) return 1;
if (grid[pos_x][pos_y] != 1) return 0; // 说明这个方格已经是遍历过的陆地
grid[pos_x][pos_y] = 2;
return dfs(grid, pos_x - 1, pos_y) + dfs(grid, pos_x + 1, pos_y) +
dfs(grid, pos_x, pos_y - 1) + dfs(grid, pos_x, pos_y + 1);
}
public:
int islandPerimeter(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
int res = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == 1) {
res += dfs(grid, i, j);
}
}
}
return res;
}
};
封闭岛屿的数目
这道题与求岛屿的数目有点像，稍有不同的是，当岛屿以地图边界为边时，此时这个岛屿不算是封闭的。
因此我们可以自然的想到，利用DFS将不算封闭的边界岛屿找出来，而在这个算法执行的过程中就会将这些岛屿修改为海洋，因此剩下的岛屿就全为封闭岛屿，计算这些剩下的岛屿即可。
class Solution {
private:
constexpr static int dx[4] = {0, -1, 0, 1};
constexpr static int dy[4] = {1, 0, -1, 0};
bool inRange(vector<vector<int>>& grid, int x, int y) {
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
return true;
}
return false;
}
void dfs(vector<vector<int>>& grid, int pox, int poy) {
if (!inRange(grid, pox, poy)) return;
if (grid[pox][poy] != 0) return;
grid[pox][poy] = 1;
for (int i = 0; i < 4; ++i) {
dfs(grid, pox + dx[i], poy + dy[i]);
}
}
public:
int closedIsland(vector<vector<int>>& grid) {
int res = 0;
int row = grid.size(), col = grid[0].size();
// 优先处理边界，将边界岛屿剔除
for (int i = 0; i < row; ++i) {
dfs(grid, i, 0);
dfs(grid, i, col - 1);
}
for (int j = 0; j < col; ++j) {
dfs(grid, 0, j);
dfs(grid, row - 1, j);
}
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == 0) {
++res;
dfs(grid, i, j);
}
}
}
return res;
}
};