相关阅读
岛屿类问题的通用解法、DFS 遍历框架
网格类问题的DFS遍历方法
网格问题的基本概念
网格问题是由一个mxn个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行搜索。 岛屿问题是一类典型的网格问题，每个格子中的数字可能是0或者1，把数字1看作是陆地，0是海洋，相邻的陆地格子就连接成一个岛屿。
岛屿问题基本都用DFS遍历解决
DFS的基本结构
网格结构要二叉树结构稍微复杂，它其实是一种简化的图结构。网格的DFS遍历，可以通过二叉树DFS遍历来类比。
二叉树遍历一般是：
function traverse(TreeNode root) {
if(!root) {
return;
}
traverse(root.left);
traverse(root.right);
}可以看出，二叉树的DFS有两个要素：访问相邻节点和判断base
对于网格的DFS，可以参考二叉树的DFS,写出网格的两个要素：
首先，网格有多少个相邻节点？
答案是上下左右四个。对于格子(r,c)来说，四个相邻的格子分别是(r-1,c)、(r+1,c)、(r,c-1)、(r,c+1)。换句话说，网格结构是四叉的
其次，网格DFS中的base是什么？从二叉树的base中对应过来，就是网格中不需要继续便利、grid[r][c]会数组下标越界异常的格子，也就是超出范围的格子。
因此，能得出初步的代码：
function dfs(grid,r,c) {
if(!inArea(grid,r,c)) {
return;
}
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(grid,r,c+1);
}
function inArea(grid,r,c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length
}如何避免重复遍历
标记已经遍历过的棋子； 0 — 海洋 1 — 陆地（未遍历过） 2 — 陆地（已遍历）
function dfs(grid,r,c) {
if(!inArea(grid,r,c)) {
return;
}
if(grid[r][c] != 1) {
return;
}
grid[r][c] = 2;
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(grid,r,c+1);
}
function inArea(grid,r,c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length
}