Connected Cells in a Grid

Sort by

recency

|

271 Discussions

|

  • + 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);
    }
    
  • + 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
    }
    
  • + 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;
    }
    
  • + 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
    
  • + 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;
    

    }