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.
To keep track of visited grid cells, just mark the original grid cell with a 0. This simplifies the code.
importjava.util.Scanner;importjava.util.ArrayList;/* Tips:1) Instead of using a "boolean[][] visited" array, we alter our original grid2) Dont create a 2-D "Point" or "Cell" class. It's not necessary.*/publicclassSolution{privatestaticintrows;// here for convenienceprivatestaticintcols;// here for conveniencepublicstaticvoidmain(String[]args){/* Read and save grid */Scannerscan=newScanner(System.in);rows=scan.nextInt();cols=scan.nextInt();intgrid[][]=newint[rows][cols];for(intgrid_i=0;grid_i<rows;grid_i++){for(intgrid_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 */publicstaticintlargestRegion(int[][]grid){intmaxRegion=0;/* From each filled cell, find the largest region from that cell */for(introw=0;row<rows;row++){for(intcol=0;col<cols;col++){if(grid[row][col]==1){intsize=findLargestRegion(grid,row,col);maxRegion=Math.max(maxRegion,size);}}}returnmaxRegion;}privatestaticintfindLargestRegion(int[][]grid,introw,intcol){/* 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){return0;}elseif(grid[row][col]==0){return0;}grid[row][col]=0;// we alter the original matrix hereintsize=1;// 1 accounts for our size/* Accounts recursively for neighbors sizes */for(intr=row-1;r<=row+1;r++){for(intc=col-1;c<=col+1;c++){size+=findLargestRegion(grid,r,c);}}returnsize;}}
Connected Cells in a Grid
You are viewing a single comment's thread. Return to all 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.
From my HackerRank Java solutions.