LeetCode -- Number of Islands

LeetCode -- Number of Islands

問題描述：


Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.


Example 1:


11110
11010
11000
00000
Answer: 1


Example 2:


11000
11000
00100
00011
Answer: 3




給定一個二維數組grid，1表示陸地，0表示海洋，求出島嶼的數量，島嶼的定義為：上下左右為海洋或超出邊界(在grid之外)。


例如對於


11000
11000
00100
00011


這個二維數組而言，由
11
11
構成了一個島嶼；中間的
1
構成了一個島嶼；最後的
11
構成了另一個島嶼，一共3個島嶼。




思路：


本題考慮的還是DFS：
1.初始化一個標記數組flag[,]
2.遍歷grid[,]，如果當前為'1'，則DFS從當前位置向上，下，左，右進行標記（注意判斷越界），如果下一個位置也為'1'，flag[row,col]=true。
這樣一來，DFS就能夠保證所有可達的'1'都被標記在flag中。
3.在遍歷grid[,]時，發現下一處未標記的'1'，進入DFS進行標記。
4.標記了多少輪，就有多少個島嶼。


實現代碼：

public class Solution {
    public int NumIslands(char[,] grid) 
    {
        var row = grid.GetLength(0);
    	var col = grid.GetLength(1);
    	
    	var flag = new bool[row, col];
    	
    	var count = 0;
    	for(var i = 0;i < row; i++){
    		for(var j = 0;j < col; j++){
    			if(grid[i,j] == '1' && !flag[i,j]){
    				count ++;
    				Mark(ref flag, grid, i, j);
    			}
    		}
    	}
    	return count;
    }


    private void Mark(ref bool[,] flag, char[,] grid, int r, int c)
    {
    	var row = flag.GetLength(0);
    	var col = flag.GetLength(1);
    	
    	if(r < 0 || c < 0 || r >= row || c >= col || grid[r,c] == '0' ||flag[r,c]){
    		return;
    	}
    	flag[r,c] = true;
    	
    	Mark(ref flag, grid, r + 1, c);
    	Mark(ref flag, grid, r - 1, c);
    	Mark(ref flag, grid, r, c + 1);
    	Mark(ref flag, grid, r, c - 1);
    }


}