Yu's Coding Garden : leetcode Questions: Number of Islands

Yu's Coding Garden : leetcode Questions: Number of Islands: "leetcode Questions: Number of Islands
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

Analysis:

This is a typical recursive problem which can be solved by either Depth First Search(DFS) or Breath First Search (BFS).

Briefly speaking, DFS is to search every possible directions(solutions) whenever meet the new one, BFS is to search and store every possible directions(solutions) using a queue usually, then search from the head of the queue each time.

In this problem, possible directions are left, right, top, bottom, with constrains that the new location is '1' and has not been visited before. Therefore, we can define a bool matrix (of same size) to store the status of each element in the grid, set it to false when it is not available(been visited).

Details can be found in the code below, which is pretty straightforward."



'via Blog this'