LintCode: Island City

Island City

Similar Problems:

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.


  1. We only consider up, down, left and right as adjacent.
  2. n <= 100, m <= 100.
  3. You can assume that the four sides of the matrix are surrounded by the sea.


Given mat =

, return 0.

There are 3 islands, but none of them contain cities.
Given mat =

, return 2.

There are 3 islands, and two of them have cities.


Credits To:

Leave me comments, if you have better ways to solve.

## Blog link:
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[0])
        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:

        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)

Share It, If You Like It.

Leave a Reply

Your email address will not be published.