HackerEarth Areas problem solution

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.

#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()