岛屿问题是经典的网格搜索问题，此类问题有通用的DFS方法。
题目有：leetcode: 200 岛屿数量，463：岛屿的周长，695：岛屿的最大面积。
leetcode200：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例：此类问题均可以用DFS求解，当搜索到某一个点时，只需要依次递归搜索其上下左右四个响铃点即可。
// 基本的 DFS 框架：每次搜索上下左右四个相邻方格
void dfs(int[][] grid, int i, int j) {
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
依据不同的题目要求，我们有不同的越界处理返回值，放到题目中细讲。
对于岛屿数量问题：只需要在访问到边界或者递归访问到水域时，直接返回即可。
访问过的点我们置0处理，防止重复访问。每次搜索到1说明发现了一块岛屿，dfs可以保证将其相邻的陆地全部搜索出来，然后置零。
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
dfs(grid, i, j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid, int i , int j){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
return;
grid[i][j] = '0';
dfs(grid, i-1, j);
dfs(grid, i+1, j);
dfs(grid, i, j-1);
dfs(grid, i, j+1);
}
}
leetcode 695：岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例：此题与上面不同之处在于，每次我们找出一块陆地时，我们需要求出其面积，即陆地的数量：作为返回值。用res记录每次dfs后返回的面积值，用ans来更新最大的面积值。
class Solution {
int count = 0;
public int maxAreaOfIsland(int[][] grid) {
int ans = 0,res = 0;
for(int i = 0;i=grid.length ||j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
else count++;
grid[i][j] = 0;//已访问标记，防止重复访问。
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
return count;
}
}
leetcode463：岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例：仔细观察，我们发现当从陆地走向水域或者边界时，会有一条边，即周长加1，因为统计即可。此处我们标记已经走过的陆地不能再用0，会与水域混淆，因此用2代替标记。
class Solution {
public int islandPerimeter(int[][] grid) {
int res = 0,ans = 0;
for(int i = 0;i < grid.length;i++){
for(int j = 0;j < grid[0].length;j++){
if(grid[i][j] == 1){
res = dfs(grid,i,j);
ans = ans + res;
return ans;
}
}
}
return 0;
}
public int dfs(int[][] grid,int i, int j){
//从陆地走向水域或者边界时，周长加一
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 1;
if(grid[i][j] != 1) return 0;
grid[i][j] = 2;//岛屿数量用0标记已走过，此处不能，因为要计算走向水域时的边
return dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
}
}
此题还有数学解法：即每个土壤四条边，每一个接壤的土壤，会减少两条边，只需要算土壤数量以及接壤土壤数量做数学减法就行了。
class Solution{
public int islandPerimeter(int[][] grid){
int count = 0,temp = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
count++;
//看右边下面是否有接壤土壤，一行一行遍历的过程可以防漏！
if(i+1 < grid.length && grid[i+1][j] == 1) temp++;
if(j+1 < grid[0].length && grid[i][j+1] == 1) temp++;
}
}
}
return 4*count - 2*temp;
}
}
