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

|

271 Discussions

|

  • tordjarv
     + 0 comments

    I seem to be the only one using the Union Find algorithm:

    #include <stdio.h>
#include <stdlib.h>

typedef struct {
        size_t *branches;
        size_t num_branches;
} forest_t;

forest_t new_forest(size_t max_num_trees) {
        forest_t forest = {.branches =
                               (size_t *)malloc(max_num_trees * sizeof(size_t)),
                           .num_branches = max_num_trees};
        for (size_t i = 0; i < max_num_trees; i++)
                forest.branches[i] = i;
        return forest;
}

size_t find_root(const forest_t forest, size_t node_index) {
        while (forest.branches[node_index] != node_index) {
                node_index = forest.branches[node_index];
        }
        return node_index;
}

void connect_trees(forest_t forest, size_t left_node, size_t right_node) {
        left_node = find_root(forest, left_node);
        right_node = find_root(forest, right_node);
        forest.branches[right_node] = left_node;
}

void free_forest(forest_t forest) {
        free(forest.branches);
}

size_t max(size_t left, size_t right) {
        return left > right ? left : right;
}

int main() {
        size_t num_rows;
        size_t num_columns;
        scanf("%lu", &num_rows);
        scanf("%lu", &num_columns);
        char *grid = (char *)malloc(num_rows * num_columns + 1);
        {
                for (size_t i = 0; i < num_rows; i++) {
                        for (size_t j = 0; j < num_columns; j++) {
                                int c;
                                scanf("%d", &c);
                                grid[i * num_columns + j] = c+'0';
                        }
                }
        }
        forest_t forest = new_forest(num_rows * num_columns);
        for (size_t i = 0; i < num_rows * num_columns; i++) {
                ssize_t row = i / num_columns;
                ssize_t col = i % num_columns;
                for (size_t k = 0; k < 8; k++) {
                        size_t j = (k + 6) % 9;
                        ssize_t row_neighbor = row + (ssize_t)(j / 3) - 1;
                        ssize_t col_neighbor = col + (ssize_t)(j % 3) - 1;
                        size_t l = row_neighbor * num_columns + col_neighbor;
                        if (row_neighbor >= 0 && row_neighbor < num_rows &&
                            col_neighbor >= 0 && col_neighbor < num_columns &&
                            grid[i] == grid[l] &&
                            find_root(forest, i) != find_root(forest, l)) {
                                connect_trees(forest, i, l);
                        }
                }
        }
        size_t *root_counts =
            (size_t *)calloc(num_rows * num_columns, sizeof(size_t));
        for (size_t i = 0; i < num_rows * num_columns; i++) {
                if (grid[i] == '1') {
                        root_counts[find_root(forest, i)]++;
                }
        }
        size_t max_count = 0;
        for (size_t i = 0; i < num_rows * num_columns; i++) {
                max_count = max(max_count, root_counts[i]);
        }
        printf("%lu\n", max_count);
}

  • 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
     + 1 comment

    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;

    }