We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Connected Cells in a Grid
  5. Discussions

Connected Cells in a Grid

  • mss2518
     + 0 comments

    Pretty standard DFS approach w/ O(1) memory trick (ignoring stack space). Recursively, the number of connected tiles is the sum of all of number of connected tiles in the immediately connected regions. A double for loop handles all of the neighbours, and we can set the matrix value to 0 when we've visited a cell, to ensure we don't visit it again.

    def connectedCell(matrix):
    M, N = len(matrix), len(matrix[0])

    def dfs(i, j):
        if i < 0 or i >= M:
            return 0
        if j < 0 or j >= N:
            return 0
        if matrix[i][j] == 0:
            return 0
        ans = 1
        matrix[i][j] = 0
        for di in range(-1, 2):
            for dj in range(-1, 2):
                ans += dfs(i + di, j + dj)
        return ans
        
    ans = 0
    for i in range(M):
        for j in range(N):
            ans = max(ans, dfs(i, j))
    return ans