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

|

270 Discussions

|

  • nissivm
     + 0 comments

    My Swift solution:

    var maxConnectedCells: Int = 0
var connectedCells: Int = 0
var grid: [[Cell]] = []
var visited: [Cell] = []
 
class Cell {
    var filled: Bool = false
    var i: Int = 0
    var j: Int = 0
}

func connectedCell(matrix: [[Int]]) -> Int {
    createCells(matrix: matrix)

    for row in grid {

        connectedCells = 0

    innerLoop: for cell in row {
            if !cell.filled { break innerLoop }
            if cell.filled && !visited.contains(where: { $0.i == cell.i && $0.j == cell.j }) {
                markCurrentCell(cell: cell)
            }
        }
    }

    return maxConnectedCells
}

private func markCurrentCell(cell: Cell) {
    visited.append(cell)
    connectedCells += 1
    let largest = max(maxConnectedCells, connectedCells)
    maxConnectedCells = largest

    exploreAround(i: cell.i, j: cell.j)
}

private func exploreAround(i: Int, j: Int) {
    let directions = [(-1, -1), (0, -1), (-1, 1), (1, 1), (0, 1), (-1, 0), (1, -1), (1, 0)]

    for direction in directions {
        let newI = i + direction.0
        let newJ = j + direction.1

        if (newI < 0) || (newI >= grid.count) {
            continue
        }

        if (newJ < 0) || (newJ >= grid[newI].count) {
            continue
        }

        let cell = grid[newI][newJ]

        guard cell.filled && !visited.contains(where: { $0.i == cell.i && $0.j == cell.j }) else {
            continue
        }

        visited.append(cell)
        connectedCells += 1
        let largest = max(maxConnectedCells, connectedCells)
        maxConnectedCells = largest

        exploreMore(cell: cell)
    }
}

private func exploreMore(cell: Cell) {
    let directions = [(-1, -1), (0, -1), (-1, 1), (1, 1), (0, 1), (-1, 0), (1, -1), (1, 0)]

    for direction in directions {
        let newI = cell.i + direction.0
        let newJ = cell.j + direction.1

        if (newI < 0) || (newI >= grid.count) {
            continue
        }

        if (newJ < 0) || (newJ >= grid[newI].count) {
            continue
        }

        let cell = grid[newI][newJ]

        guard cell.filled && !visited.contains(where: { $0.i == cell.i && $0.j == cell.j }) else {
            continue
        }

        visited.append(cell)
        connectedCells += 1
        let largest = max(maxConnectedCells, connectedCells)
        maxConnectedCells = largest
    
        exploreMore(cell: cell)
    }
}

private func createCells(matrix: [[Int]]) {
    var collumns: [[Cell]] = []
    for (i, _) in matrix.enumerated() {
        var row: [Cell] = []
        for (j, _) in matrix[i].enumerated() {
            let cell = Cell()
            cell.filled = matrix[i][j] == 1 ? true : false
            cell.i = i
            cell.j = j
            row.append(cell)
        }
        collumns.append(row)
    }
    grid = collumns
}

  • ausshadu
     + 0 comments

    JavaScript solution inspired by other folks

    function connectedCell(matrix) {
  let largestArea = 0;
  const rows = matrix.length;
  const cols = matrix[0].length;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === 1) {
        depthFirstSearch(matrix, i, j, 0); // Start with area as 0
      }
    }
  }

  function depthFirstSearch(matrix, i, j, currentCell) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[i][j] === 0) {
      return;
    }

    currentCell++;
    largestArea = Math.max(largestArea, currentCell);
    matrix[i][j] = 0;

    // Upper Row
    depthFirstSearch(matrix, i - 1, j - 1, currentCell);
    depthFirstSearch(matrix, i - 1, j, currentCell);
    depthFirstSearch(matrix, i - 1, j + 1, currentCell);

    // Current Row
    depthFirstSearch(matrix, i, j - 1, currentCell);
    depthFirstSearch(matrix, i, j + 1, currentCell);

    // Lower Row
    depthFirstSearch(matrix, i + 1, j - 1, currentCell);
    depthFirstSearch(matrix, i + 1, j, currentCell);
    depthFirstSearch(matrix, i + 1, j + 1, currentCell);

    matrix[i][j] = 1;
  }

  return largestArea;
}

  • 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

  • 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];
}