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.
Connected Cells in a Grid
Connected Cells in a Grid
+ 4 comments A trick to avoid the boundary check: add an artificial boundary of 0 around the whole matrix.
+ 10 comments I used Dfs
#include <bits/stdc++.h> using namespace std; int a[100][100], vis[100][100]; int r, c, TotalOne; int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; bool check(int x, int y) { return (x >= 0 && x < r && y >= 0 && y < c); } void dfs(int i, int j) { TotalOne++; vis[i][j] = 1; for(int k = 0; k < 8; k++) { int x = i + dx[k]; int y = j + dy[k]; if(check(x, y) && vis[x][y] == 0 && a[x][y] == 1) dfs(x, y); } } int main() { cin >> r >> c; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> a[i][j]; int mx = INT_MIN; for(int i = 0; i < r; i++) { for(int j = 0; j < c; j++) { if(vis[i][j] == 0 && a[i][j] == 1) { TotalOne = 0; dfs(i, j); if(TotalOne > mx) mx = TotalOne; } } } cout << mx; return 0; }
+ 5 comments Java solution - passes 100% of test cases
To keep track of visited grid cells, just mark the original grid cell with a 0. This simplifies the code.
import java.util.Scanner; import java.util.ArrayList; /* Tips: 1) Instead of using a "boolean[][] visited" array, we alter our original grid 2) Dont create a 2-D "Point" or "Cell" class. It's not necessary. */ public class Solution { private static int rows; // here for convenience private static int cols; // here for convenience public static void main(String[] args) { /* Read and save grid */ Scanner scan = new Scanner(System.in); rows = scan.nextInt(); cols = scan.nextInt(); int grid[][] = new int[rows][cols]; for (int grid_i = 0; grid_i < rows; grid_i++) { for (int grid_j = 0; grid_j < cols; grid_j++) { grid[grid_i][grid_j] = scan.nextInt(); } } scan.close(); System.out.println(largestRegion(grid)); } /* Returns the size of the largest region */ public static int largestRegion(int [][] grid) { int maxRegion = 0; /* From each filled cell, find the largest region from that cell */ for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (grid[row][col] == 1) { int size = findLargestRegion(grid, row, col); maxRegion = Math.max(maxRegion, size); } } } return maxRegion; } private static int findLargestRegion(int [][] grid, int row, int col) { /* Pro tip: put boundary checks at top of recursive call, instead of before doing recursive call */ if (row < 0 || row >= rows || col < 0 || col >= cols) { return 0; } else if (grid[row][col] == 0) { return 0; } grid[row][col] = 0; // we alter the original matrix here int size = 1; // 1 accounts for our size /* Accounts recursively for neighbors sizes */ for (int r = row - 1; r <= row + 1; r++) { for (int c = col - 1; c <= col + 1; c++) { size += findLargestRegion(grid, r, c); } } return size; } }
From my HackerRank Java solutions.
+ 2 comments My solution using floodfill in Python:
n=int(input()) m=int(input()) def floodfill(i,j): if i>=n or j>=m or mat[i][j]==-1 or mat[i][j]==0 or i<0 or j<0: return 0 else: mat[i][j]=-1 return 1+(floodfill(i+1,j)+floodfill(i-1,j)+floodfill(i,j+1)+floodfill(i,j-1)+floodfill(i+1,j-1)+floodfill(i+1,j+1)+floodfill(i-1,j-1)+floodfill(i-1,j+1)) mat=[] res=-999 for i in range(n): mat.append([int(x) for x in input().split()]) for i in range(n): for j in range(m): res=max(res,floodfill(i,j)) print(res)
+ 2 comments Solved with Union/Find
Load more conversations
Sort 227 Discussions, By:
Please Login in order to post a comment