(Hacker Hank) Connected Cell in a Grid - Solution

Link to the problem: https://www.hackerrank.com/challenges/connected-cell-in-a-grid

The problem asks to find the largest number of connected cells in the matrix. It made me think that given a position in the matrix, I should explore as far as possible in order to find all the numbers '1' connected. This approach is known as Depth-First Search.


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static int[][] matrix;
    public static boolean[][] visited;
    public static int numRows;
    public static int numCols;
    public static int connectedCells;
    public static int[] vi = {-1,-1,-1,0,0,1,1,1};
    public static int[] vj = {-1,0,1,-1,1,-1,0,1};
   
    public static void dfs(int currI, int currJ) {
        if (currI < 0 || currJ < 0 || currI >= numRows || currJ >= numCols || visited[currI][currJ] || matrix[currI][currJ] == 0) {
            return;
        }
       
        connectedCells++;
        visited[currI][currJ] = true;
        for (int i = 0; i < 8; i++) {
            int nextI = currI+vi[i];
            int nextJ = currJ+vj[i];
            dfs(nextI, nextJ);
        }
    }
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        numRows = sc.nextInt();
        numCols = sc.nextInt();
        matrix = new int[numRows][numCols];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
       
        int maxConnectedCells = 0;
        visited = new boolean[numRows][numCols];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                connectedCells = 0;
                dfs(i, j);
                if (connectedCells > maxConnectedCells) {
                    maxConnectedCells = connectedCells;
                }
            }
        }
       
        System.out.println(maxConnectedCells);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução