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.
Connected Cells in a Grid
Connected Cells in a Grid
Sort by
recency
|
272 Discussions
|
Please Login in order to post a comment
visited_nodes=[] region_count=0 def dfs(matrix,i,j): global region_count
def connectedCell(matrix): global region_count global visited_nodes max_count=0; matrix_rows=len(matrix) matrix_columns=len(matrix[0]) visited_nodes=[] for i in range(matrix_rows): for j in range(matrix_columns): if matrix[i][j]==1 and not (i,j) in visited_nodes: region_count=1 visited_nodes.append((i,j)) dfs(matrix,i,j) print(f"{i}-{j} ===> {region_count}") if region_count>max_count: max_count=region_count region_count=1 return max_count
I seem to be the only one using the Union Find algorithm:
My Swift solution:
JavaScript solution inspired by other folks
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.