In this HackerRank DFS: Connected Cell in a Grid Interview preparation kit problem there is Given an n x m matrix, find and print the number of cells in the largest region in the matrix.
Problem solution in Python programming.
def getAdjacentNodes(matrix, i, j):
s = set()
if i - 1 >= 0:
if matrix[i-1][j] == 1:
s = s.union([(i-1, j)])
if j - 1 >= 0:
if matrix[i-1][j-1] == 1:
s = s.union([(i-1, j-1)])
if j + 1 < len(matrix[i]):
if matrix[i-1][j+1] == 1:
s = s.union([(i-1, j+1)])
if i + 1 < len(matrix):
if matrix[i+1][j] == 1:
s = s.union([(i+1, j)])
if j - 1 >= 0:
if matrix[i+1][j-1] == 1:
s = s.union([(i+1, j-1)])
if j + 1 < len(matrix[i]):
if matrix[i+1][j+1] == 1:
s = s.union([(i+1, j+1)])
if j - 1 >= 0:
if matrix[i][j-1] == 1:
s = s.union([(i, j-1)])
if j + 1 < len(matrix[i]):
if matrix[i][j+1] == 1:
s = s.union([(i, j+1)])
return s
def matrixToAdjacencyList(matrix):
g = {}
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 1:
g[(i, j)] = getAdjacentNodes(matrix, i, j)
return g
def dfs(graph):
def helper(start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return len(visited)
return helper
def getBiggestRegion(grid):
graph = matrixToAdjacencyList(grid)
sizes = []
gdfs = dfs(graph)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 1:
sizes.append(gdfs((i, j)))
return max(sizes)
n = int(input().strip())
m = int(input().strip())
grid = []
for grid_i in range(n):
grid_t = list(map(int, input().strip().split(' ')))
grid.append(grid_t)
print(getBiggestRegion(grid))
Problem solution in Java Programming.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static boolean[] marked;
static int[] id;
static int[] size;
static int count;
private static int largestConnectedComponentCount(Graph g) {
List<Integer> nodes = new ArrayList<>();
int i = 0;
for (boolean e : g.enabled) {
if (e) { nodes.add(i); }
i++;
}
marked = new boolean[g.enabled.length];
id = new int[g.enabled.length];
size = new int[g.enabled.length];
count = 0;
for (int v : nodes) {
if (!marked[v]) {
dfs(g, v);
count++;
}
}
return Arrays.stream(size).max().orElse(0);
}
// depth-first search
private static void dfs(Graph g, int v) {
marked[v] = true;
id[v] = count;
size[count]++;
g.adj.get(v)
.stream()
.filter(w -> !marked[w])
.forEach(w -> dfs(g, w));
}
private static class Graph {
boolean[] enabled;
List<Set<Integer>> adj;
Graph(int size) {
enabled = new boolean[size];
adj = new ArrayList<>();
for (int i = 0; i < size; i++) {
adj.add(new HashSet<>());
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int i = 0;
Graph g = new Graph(n * m);
for(int row = 0; row < n; row++){
for(int col = 0; col < m; col++) {
int val = in.nextInt();
if (val == 1) {
g.enabled[i] = true;
int prev = i - 1;
int upLeft = i - m - 1;
int up = i - m;
int upRight = i - m + 1;
if (col > 0 && g.enabled[prev]) {
g.adj.get(prev).add(i);
g.adj.get(i).add(prev);
}
if (col > 0 && row > 0 && g.enabled[upLeft]) {
g.adj.get(upLeft).add(i);
g.adj.get(i).add(upLeft);
}
if (row > 0 && g.enabled[up]) {
g.adj.get(up).add(i);
g.adj.get(i).add(up);
}
if (col < m - 1 && row > 0 && g.enabled[upRight]) {
g.adj.get(upRight).add(i);
g.adj.get(i).add(upRight);
}
}
i++;
}
}
System.out.println(largestConnectedComponentCount(g));
}
}
Problem solution in C++ programming.
#include<bits/stdc++.h>
using namespace std;
int a[10][10];
int count(int i,int j,int n, int m)
{
int answer = 0;
if(a[i][j] == 0)
return 0;
if(i<0 or j<0 or i>= n or j >=m)
return 0;
if(a[i][j] == 1)
{
answer++;
a[i][j]--;
}
answer += count(i-1,j-1,n,m);
answer += count(i-1,j,n,m);
answer += count(i-1,j+1,n,m);
answer += count(i,j-1,n,m);
answer += count(i,j+1,n,m);
answer += count(i+1,j-1,n,m);
answer += count(i+1,j,n,m);
answer += count(i+1,j+1,n,m);
return answer;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int max = -1,ans;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
ans = count(i,j,n,m);
if(ans > max)
max = ans;
}
cout<<max;
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define RUN_TEST_CASES(VAR) int VAR##_total; scanf("%d", & VAR##_total);
for(int VAR=1; VAR<=VAR##_total; ++VAR)
typedef unsigned long long ull;
int get_area_size(int matrix[10][10], int rows, int cols, int row, int col)
{
if (row < 0 || row >= rows) return 0;
if (col < 0 || col >= cols) return 0;
if (matrix[row][col] != 1) return 0;
matrix[row][col] = 0; // visited
return 1
+ get_area_size(matrix, rows, cols, row - 1, col - 1)
+ get_area_size(matrix, rows, cols, row - 1, col)
+ get_area_size(matrix, rows, cols, row - 1, col + 1)
+ get_area_size(matrix, rows, cols, row, col - 1)
+ get_area_size(matrix, rows, cols, row, col + 1)
+ get_area_size(matrix, rows, cols, row + 1, col - 1)
+ get_area_size(matrix, rows, cols, row + 1, col)
+ get_area_size(matrix, rows, cols, row + 1, col + 1)
;
}
int main()
{
#ifdef _DEBUG
char FNAME[250];
strcpy(FNAME, __FILE__);
strcpy(strchr(FNAME, '.'), ".txt");
freopen(FNAME, "rt", stdin);
#endif
int matrix[10][10];
int rows, cols;
scanf("%d %d", &rows, &cols);
for (int row = 0; row < rows; ++row)
for (int col = 0; col < cols; ++col)
scanf("%d", &matrix[row][col]);
int largest_area = 0;
for (int row = 0; row < rows; ++row)
{
for (int col = 0; col < cols; ++col)
{
if (matrix[row][col] != 1) continue;
int area_size = get_area_size(matrix, rows, cols, row, col);
if (area_size > largest_area)
largest_area = area_size;
}
}
printf("%d", largest_area);
}
Problem solution in JavaScript programming.
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
var isValid = function(x, y, n, m) {
return (x >= 0 && y >= 0 && x < n && y < m);
}
var visit = function(x, y, grid, visited, n, m) {
if (grid[x][y] === 1 && !visited[x][y]) {
var count = 1;
visited[x][y] = true;
for (var i = x - 1; i <= x + 1; i++) {
for (var j = y - 1; j <= y + 1; j++) {
if (isValid(i, j, n, m)) {
count += visit(i, j, grid, visited, n, m);
}
}
}
return count;
} else {
return 0;
}
}
function main() {
var n = parseInt(readLine());
var m = parseInt(readLine());
var grid = [];
for(grid_i = 0; grid_i < n; grid_i++){
grid[grid_i] = readLine().split(' ');
grid[grid_i] = grid[grid_i].map(Number);
}
var visited = [];
for (var i = 0; i < grid.length; i++) {
visited.push([]);
}
var max = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
var count = visit(i, j, grid, visited, n, m);
max = Math.max(count, max);
}
}
console.log(max);
}