Consider a matrix with N rows and M columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are connected, they form a region. The task is to find the unit area of the largest region. - Codeprg

Breaking

programing News Travel Computer Engineering Science Blogging Earning

Saturday, 13 June 2020

Consider a matrix with N rows and M columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are connected, they form a region. The task is to find the unit area of the largest region.

Consider a matrix with N rows and M columns, where each cell contains either a ‘0’ or a ‘1’, and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are connected, they form a region. The task is to find the unit area of the largest region.

Here is a simple and easy approach using dfs with execution time is 0.01s.

Mug, Quotes, Text, Phrase, Word, Sentence, Saying
#include <bits/stdc++.h>

using namespace std;

void dfs(vector < int > a[], int n, int m, int i, int j, int & p) {
    if (i < 0 || i > n || j < 0 || j > m || a[i][j] == 0 || a[i][j] == -1)
        return;

    ++p;
    a[i][j] = -1;

    dfs(a, n, m, i + 1, j, p);
    dfs(a, n, m, i - 1, j, p);
    dfs(a, n, m, i, j + 1, p);
    dfs(a, n, m, i, j - 1, p);
    dfs(a, n, m, i - 1, j - 1, p);
    dfs(a, n, m, i - 1, j + 1, p);
    dfs(a, n, m, i + 1, j - 1, p);
    dfs(a, n, m, i + 1, j + 1, p);

}

int main() {
    //code
    int t;
    cin >> t;
    while (t--) {
        int n, m, l;
        cin >> n >> m;

        // vector<vector<int> > v(n,vector<int>(m));

        // for(int i=0;i<n;++i)
        // {
        //     for(int j=0;j<m;++j)
        //     {
        //         cin>>l;

        //         v[i][j]=l;
        //     }
        // }
        vector < int > a[n];
        int i, j;
        for (i = 0; i < n; i++) {
            vector < int > temp(m, 0);
            a[i] = temp;
            for (j = 0; j < m; j++)
                cin >> a[i][j];
        }

        int ans = 0;
        int p = 0;

        for (i = 0; i < n; ++i)
            for (j = 0; j < m; ++j)
                if (a[i][j] == 1) {
                    p = 0;
                    dfs(a, n - 1, m - 1, i, j, p);
                    ans = max(ans, p);
                }

        cout << ans << endl;

    }

    return 0;
}