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

|

274 Discussions

|

  • zettix1
     + 0 comments

    With aux class so I can make a tupple without resorting to using stings and split():

    class OneSpot {
    int x;
    int y;
    public OneSpot(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public boolean equals(Object o) {
        OneSpot s = (OneSpot) o;
        return (s.x == x && s.y== y);
    }
    @Override
    public int hashCode() {
        return y * 100 + x;
    }
}


class Result {

    /*
     * Complete the 'connectedCell' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY matrix as parameter.
     */
    public static void grow(OneSpot spot, Set<OneSpot> ones, int xmax,
                            int ymax, Set<OneSpot> seen,
        Set<OneSpot> ourgang) {
            for (int dx = -1 ; dx < 2; dx++) {
                for (int dy = -1; dy < 2; dy++) {
                    int nx = spot.x + dx;
                    int ny = spot.y + dy;
                    OneSpot nspot = new OneSpot(nx, ny);
                    if (ones.contains(nspot) && ! seen.contains(nspot)) {
                        ourgang.add(nspot);
                        seen.add(nspot);
                        grow(nspot, ones, xmax, ymax, seen, ourgang);
                    }
                }
            }   
        }

    public static int connectedCell(List<List<Integer>> matrix) {
    // Write your code here
        Set<OneSpot> ones = new HashSet<>();
        int ymax = matrix.size() - 1;
        int xmax = matrix.get(0).size() - 1;
        for (int y = 0; y <= ymax; y++) {
            for (int x = 0; x <= xmax; x++) {
                if (matrix.get(y).get(x) == 1) {
                    ones.add(new OneSpot(x, y));
                }
            }
        }
        int size = 0;
        Set<OneSpot> seen = new HashSet<>();
        for (OneSpot spot : ones) {
            Set<OneSpot> ourgang = new HashSet<>();
            if (seen.contains(spot)) {
                continue;
            }
            ourgang.add(spot);
            seen.add(spot);
            grow(spot, ones, xmax, ymax, seen, ourgang);
            if (ourgang.size() > size) {
                size = ourgang.size();
            }
        }
        return size;
    }
}

  • CYS1B_1720109
     + 0 comments

    Solution in Python3:

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'connectedCell' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY matrix as parameter.
#

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:
            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)
            n = len(ll)
        l.append(len(ll))   
    return max(l)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    m = int(input().strip())

    matrix = []

    for _ in range(n):
        matrix.append(list(map(int, input().rstrip().split())))

    result = connectedCell(matrix)

    fptr.write(str(result) + '\n')

    fptr.close()

  • dasspradipta
     + 0 comments

    visited_nodes=[] region_count=0 def dfs(matrix,i,j): global region_count

    for p in range(-1,2):
    for q in range(-1,2):
        if i+p>=0 and i+p<len(matrix) and j+q>=0 and j+q<len(matrix[0]):
            if matrix[i+p][j+q]==1 and not (i+p,j+q) in visited_nodes:
                print(i+p,j+q)
                visited_nodes.append((i+p,j+q))
                region_count+=1
                dfs(matrix,i+p,j+q)

    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

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