**小白都能看得懂的題解**
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274823.html
標籤：其他