- Number of Islands
- Series: Island & Follow-up
- Review: Graph Problems
- Review: BFS Problems
- Tag: #graph, #dfs, #bfs, #island
Given a matrix of size n x m, the elements in the matrix are 0,1,2.
0 for the sea, 1 for the island, and 2 for the city on the island(You can assume that 2 is built on 1, ie 2 also represents the island).
If two 1 are adjacent, then these two 1 belong to the same island. Find the number of islands with at least one city.
- We only consider up, down, left and right as adjacent.
- n <= 100, m <= 100.
- You can assume that the four sides of the matrix are surrounded by the sea.
Given mat = [ [1,1,0,0,0], [0,1,0,0,1], [0,0,0,1,1], [0,0,0,0,0], [0,0,0,0,1] ]
, return 0.
Explanation: There are 3 islands, but none of them contain cities.
Given mat = [ [1,1,0,0,0], [0,1,0,0,1], [0,0,2,1,2], [0,0,0,0,0], [0,0,0,0,2] ]
, return 2.
Explanation: There are 3 islands, and two of them have cities.
Credits To: lintcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/island-city class Solution: """ @param grid: an integer matrix @return: an integer """ def numIslandCities(self, grid): ## Basic Ideas: dfs ## Complexity: Time O(m*n), Space O(1) row_count = len(grid) if row_count == 0: return 0 col_count = len(grid) self.count = 0 for i in range(row_count): for j in range(col_count): if grid[i][j] in [1, 2]: self.first_found = True self.dfs(grid, i, j, row_count, col_count) return self.count def dfs(self, grid, i, j, row_count, col_count): if i<0 or i>=row_count or \ j<0 or j>=col_count: return if grid[i][j] not in [1, 2]: return if grid[i][j] == 2 and self.first_found: self.count += 1 self.first_found = False grid[i][j] = -1 self.dfs(grid, i, j+1, row_count, col_count) self.dfs(grid, i, j-1, row_count, col_count) self.dfs(grid, i-1, j, row_count, col_count) self.dfs(grid, i+1, j, row_count, col_count)