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

Sort by

recency

|

267 Discussions

|

  • dotaikhoa
     + 0 comments

    c++ using bfs (breath first search) approach

    define pii pair

    define mk make_pair

    int bfs(int r, int c, vector> &mat, vector> &vis, int n, int m) { int surf = 0; queue q; q.push(mk(r,c)); // cout << "starting " << r << " "< 

    pii cur;
while (!q.empty()) {
    cur = q.front();
    int cr = cur.first;
    int cc = cur.second; 
    q.pop();

    if (!vis[cr][cc]) {
        vis[cr][cc]=true;
        // cout << "visiting " << cr << " " << cc << '\n';
        surf++;

        if (cr-1 >= 0) {
            if (mat[cr-1][cc]) q.push(mk(cr-1,cc));

            if (cc-1 >= 0 and mat[cr-1][cc-1]) q.push(mk(cr-1,cc-1));

            if (cc+1 < m and mat[cr-1][cc+1]) q.push(mk(cr-1,cc+1));
        }
        if (cr+1 < n) {
            if (mat[cr+1][cc]) q.push(mk(cr+1,cc));

            if (cc-1 >= 0 and mat[cr+1][cc-1]) q.push(mk(cr+1,cc-1));

            if (cc+1 < m and mat[cr+1][cc+1]) q.push(mk(cr+1,cc+1));
        }
        if (cc-1 >= 0) {
            if (mat[cr][cc-1]) q.push(mk(cr,cc-1));

            // if (cr-1 >= 0 and mat[cr-1][cc-1]) q.push(mk(cr-1,cc-1));

            // if (cr+1 < m and mat[cr+1][cc+1]) q.push(mk(cr+1,cc+1));
        }
        if (cc+1 < m) {
            if (mat[cr][cc+1]) q.push(mk(cr,cc+1));

            // if (cr-1 >= 0 and mat[cr-1][cc+1]) q.push(mk(cr-1,cc+1));
            // 
            // if (cc+1 < m and mat[cr-1][cc+1]) q.push(mk(cr-1,cc+1));
        }
    }
}

return surf;

    }

    int connectedCell(vector> matrix) { int n = matrix.size(), m = matrix[0].size(); vector> vis(n, vector(m,false));

    int res = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (matrix[i][j] and !vis[i][j]) {
            res = max(res,bfs(i,j,matrix,vis,n,m));
        }
    }
}
return res;

    }

  • touseefnaveed135
     + 0 comments

    C++ solution using backtracking(similar to rat in a maze)

    int maze(vector<vector<int>> &matrix,int i,int j){
    if(i>=0 && i<matrix.size() && j>=0 &&
     j<matrix[0].size() && matrix[i][j]!=0){
        matrix[i][j]--;
        return (1+maze(matrix,i-1,j)+maze(matrix,i+1,j)+
        maze(matrix,i,j-1)+maze(matrix,i,j+1)+maze(matrix,i-1,j-1)+
        maze(matrix,i-1,j+1)+maze(matrix,i+1,j-1)+
        maze(matrix,i+1,j+1));
    }
    else{
        return 0;
    }
}

int connectedCell(vector<vector<int>> matrix) {
    vector<int>v;
    for(int i=0;i<matrix.size();i++){
        for(int j=0;j<matrix[0].size();j++){
            if(matrix[i][j]==1){
                v.push_back(maze(matrix,i,j));
            }
        }
    }
    sort(v.begin(),v.end());
    if(v.empty()) return 0;
    else return v[v.size()-1];
}

  • shreyavishwalin1
     + 0 comments
    def connectedCell(matrix):
    def dfs(matrix, visited, i, j):
        # Stack for DFS
        stack = [(i, j)]
        count = 0

        while stack:
            x, y = stack.pop()
            if not (0 <= x < n and 0 <= y < m) or visited[x][y] or matrix[x][y] == 0:
                continue

            visited[x][y] = True
            count += 1

            # Check all 8 possible directions
            for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
                stack.append((x + dx, y + dy))

        return count

    n = len(matrix)
    m = len(matrix[0])
    visited = [[False] * m for _ in range(n)]
    max_region = 0

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1 and not visited[i][j]:
                size_of_region = dfs(matrix, visited, i, j)
                max_region = max(max_region, size_of_region)

    return max_region

  • jpan3
     + 0 comments
    def connectedCell(matrix):
    # Write your code here
    ones = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 1:
                ones.append((i, j))
    l = []
    while ones != []:
        one = ones.pop(0)
        ll = [one]
        m = 1
        n = 0
        while n != m:
            #count pre expansion
            m = len(ll)
            for one in ll:
                i, j = one[0], one[1]
                neighbors = [(i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)]
                for neighbor in neighbors:
                    if neighbor in ones:
                        ones.remove(neighbor)
                        ll.append(neighbor)
            #count post expansion
            n = len(ll)
        l.append(len(ll))   
    return max(l)

  • gtai_quant
     + 0 comments
    from collections import deque


def connectedCell(matrix):
    visited = [[True if cell == 0 else False for cell in row] for row in matrix]
    max_num = 0
    
    r, c = len(matrix), len(matrix[0])
    directions = ((0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, -1), (-1, 1), (1, 1))
    
    for i in range(r):
        for j in range(c):
            if visited[i][j]:
                continue
                
            # filled cell found
            count = 0
            queue = deque([(i, j)])
            visited[i][j] = True
            while queue:
                x, y = queue.popleft()
                count += 1
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                        queue.append((nx, ny))
                        visited[nx][ny] = True
            
            max_num = max(max_num, count)
            
    return max_num