In this HackerEarth Areas problem solution You are given a 2D grid. A '#' represents an obstacle and a '.' represents free space. You need to find the areas of the disconnected components. The cells (i+1, j), (i, j+1), (i-1, j), (i, j-1) are the adjacent to the cell (i, j).

There are multiple test cases in this problem.


HackerEarth Areas problem solution


HackerEarth Areas problem solution.

#include <bits/stdc++.h>
using namespace std;

#define IO \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e2+5;

int n, m;
vector<vector<char> > arr(N, vector<char> (N, '-'));
vector<vector<bool> > vis(N, vector<bool> (N, false));

bool is_valid(int x, int y){
if(0 <= x
and x <= n-1
and 0 <= y
and y <= m-1
and vis[x][y] == false
and arr[x][y] == '.'){
return true;
}
return false;
}

int area = 0;
void dfs(int x, int y){
area++;
vis[x][y] = true;
for(int k = 0; k < 4; k++){
if(is_valid(x+dx[k], y+dy[k])){
dfs(x+dx[k], y+dy[k]);
}
}
return;
}

main()
{
IO;
#ifndef ONLINE_JUDGE
freopen("sample_input.txt", "r", stdin);
freopen("sample_output.txt", "w", stdout);
#endif
int t;
cin >> t;
while(t--){
vis.assign(N, vector<bool> (N, false));
cin >> n >> m;

for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> arr[i][j];
}
}
int k = 0;
vector<int> ans;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(is_valid(i, j)){
area = 0;
k++;
dfs(i, j);
ans.push_back(area);
}
}
}

cout << k << '\n';
sort(ans.begin(), ans.end());
for(auto i: ans){
cout << i << ' ';
}
cout << '\n';
}

return 0;
}

Second solution

import sys
sys.setrecursionlimit(100000)
t = int(input())
while t > 0:
t -= 1
[n, m] = map(int, input().split())
a = []

def dfs(i, j):
if i < 0 or j < 0 or i >= n or j >= m or a[i][j] == '#':
return 0
a[i][j] = '#'
ans = 1
for dir in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
ans += dfs(i + dir[0], j + dir[1])
return ans

for i in range(n):
a.append(list(input()))
ans = []
for i in range(n):
for j in range(m):
if a[i][j] == '.':
ans += [dfs(i, j)]
print(len(ans))
ans.sort()
for i in ans:
print(i, end=" ")
print()