FloodFill 算法（leetcode200）

给定一个二维数组，只含有0和1两个字符，其中1代表陆地，0代表水域，横向和纵向的陆地连接成岛屿，被水域分隔开。问给出的地图中有多少岛屿。

想象上面是一个地图，棕色的是陆地，蓝色的是海洋，现在滴一滴墨水到第一个点，然后墨水蔓延到小岛的所有地方。

其实求岛屿就是对所有点进行一次深度优先遍历。对于每个点，一旦没有访问过而且也是陆地的话就也对它进行标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
vector<vector<bool>> visited;
bool isArea(int x,int y)
{
    return x>=0&&x<m&&y>=0&&y<n;
}
//从grid[x][y]的位置开始，进行floodfill.
void dfs(vector<vector<char>>& grid, int x,int  y)
{
    visited[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int newx =x+d[i][0];
        int newy =y+d[i][1];
        if(isArea(newx,newy)&&!visit[newx][newy]&&grid[newx][newy]=='1')//递归终止条件包含在if条件中。
        {
            dfs(grid,newx,newy);
            //因为要floodfill，所以这visit是不用回溯的。
        }
    }
    return ;
}
int numberisland(vector<vector<char>> & grid)
{
    m=grid.size();
    if(m==0) return 0;
    n=grid.size();
    visited =vector<vector<bool> >(m,vector<bool>(n,false));
    int res =0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            if(grid[i][j]=='1'&& !visited[i][j])
            {
                res++;
                dfs(grid,i,j); //floodfill
            }
        }
}