leetcode岛屿数量(超级详细注释）(c语言）

			**小白都能看得懂的题解**

leetcode第200题岛屿数量

解题方法：BFS和DFS(广度优先搜索和深度优先搜索)
题目描述：

eg:

1.BFS
//广度优先搜索
//c语言自造链队列
//链队列辅助
typedef struct quelist{
    int r;
    int c;
    struct quelist *next;
}quelist;

//申请一个节点
void init(quelist **p,int r,int c){
    (*p)=(quelist *)malloc(sizeof(quelist));
    (*p)->r=r;
    (*p)->c=c;
    (*p)->next=NULL;
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    int row=gridSize;
    int col=*gridColSize;
    if(!row) return 0;
    struct quelist *queleft=NULL,*queright=NULL;//分别指向队列的队头和队尾
    int num_lands=0;//用于记录岛屿的个数
    for(int i=0;i<row;++i){
        for(int j=0;j<col;++j){
            if(grid[i][j]=='1'){
                ++num_lands;
                grid[i][j]='0';//已经访问过的标记为’0‘
                init(&queright,i,j);//将这个方格入队；
                queleft=queright;//每次都要初始化队头和队尾指针指向一个位置
                //广度优先开始
                while(queleft){
                    int rr=queleft->r;//rr是队头元素的行标，cc是队头元素的列标
                    int cc=queleft->c;
                    //下面才是真正开始广度优先搜索
                    if(rr-1>=0&&grid[rr-1][cc]=='1'){
                        grid[rr-1][cc]='0';
                        init(&(queright->next),rr-1,cc);
                        queright=queright->next;
                    }
                    if(rr+1<row&&grid[rr+1][cc]=='1'){
                        grid[rr+1][cc]='0';
                        init(&(queright->next),rr+1,cc);
                        queright=queright->next;
                    }
                    if(cc-1>=0&&grid[rr][cc-1]=='1'){
                        grid[rr][cc-1]='0';
                        init(&(queright->next),rr,cc-1);
                        queright=queright->next;
                    }
                    if(cc+1<col&&grid[rr][cc+1]=='1'){
                        grid[rr][cc+1]='0';
                        init(&(queright->next),rr,cc+1);
                        queright=queright->next;
                    }  
                    queleft=queleft->next;//访问（i，j）元素的周围的元素后，开始周围的元素的广度优先搜索  
                }
            }
        }
    }
    return num_lands;
}

 2.DFS

//尝试优先搜索
//系统栈
//递归的思想
void dfs(char **grid,int row,int col,int r,int c){
	//递归
    grid[r][c]='0';
    if(r-1>=0&&grid[r-1][c]=='1') dfs(grid,row,col,r-1,c);
    if(r+1<row&&grid[r+1][c]=='1') dfs(grid,row,col,r+1,c);
    if(c-1>=0&&grid[r][c-1]=='1') dfs(grid,row,col,r,c-1);
    if(c+1<col&&grid[r][c+1]=='1') dfs(grid,row,col,r,c+1);
}
int numIslands(char** grid, int gridSize, int* gridColSize){
    int row=gridSize;
    int col=*gridColSize;
    if(!row) return 0;
    int numLands=0;
    for(int i=0;i<row;++i){
        for(int j=0;j<col;++j){
            if(grid[i][j]=='1'){
                ++numLands;
                dfs(grid,row,col,i,j);
            }
        }
    }
    return numLands;
}