HackerEarth Oliver and the battle problem solution

In this HackerEarth Oliver and the battle problem solution Colonel Oliver and his battalion were in midst of a battle against an extraterrestrial species Zomni. The Colonel has to win the battle at any cost to save all of humanity. He was short of soldiers, however, he had a very powerful weapon bazooka which could be used only once during the war.

The Zomni army was divided into small troops scattered at different locations (which can be contained in a N x M battle ground). The bazooka, once launched on some troop is capable of killing all the Zomnis of that troop at a time but cannot harm any Zomni soldier in other troops.

The war is coming to an end and the Colonel is about to lose. He has only one bazooka but something he knows for sure is that if he is able to kill the maximum possible soldiers with this bazooka, he and his soldiers definitely have a chance of winning the battle.

So, the Colonel seeks your help in finding out the maximum number of Zomnis he can kill in one strike of the bazooka and also the total number of Zomni troops gathered against them so that he can divide his battalion efficiently (the troop killed by the bazooka should also be included).

Two Zomni soldiers belong to the same troop if they are at adjacent positions in the battle ground. Therefore, any soldier who is not at some boundary of the battle ground can have a maximum of 8 adjacent soldiers.

HackerEarth Oliver and the battle problem solution.

#include<bits/stdc++.h>
using namespace std;
int n,m;
int mat[1002][1002];
int visited[1002][1002];

int findans(int x, int y)   // counts the number of soldiers in a troop and marks each troop visited in the visited matrix
{
    visited[x][y] = 1;
    int nodecount = 1;  // counts the number of soldiers in a troop

    queue<pair<int,int> > q;
    q.push(make_pair(x,y));

    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = -1 ; i<=1; i++ )
            for(int j = -1; j<=1; j++)
                if(!visited[x+i][y+j] && mat[x+i][y+j])
                {
                    nodecount++;
                    q.push(make_pair(x+i,y+j));
                    visited[x+i][y+j] = 1;
                }
    }

    return nodecount;
}

int main()
{
    int t;
    scanf("%d",&t);

    while(t--)
    {
        scanf("%d%d",&n,&m);

        memset(mat,0,sizeof(mat));
        memset(visited,0,sizeof(visited));

        for(int i = 1; i<=n ; i++)
            for(int j = 1; j<= m; j++)
                scanf("%d",&mat[i][j]);

        int ans = 0;        // maintains the maximum number of soldiers in any troop
        int counter = 0;    // counts the total number of troops
        for(int i = 1; i <= n ; i++)
            for(int j = 1; j<= m; j++)
            {
                if(!visited[i][j] && mat[i][j])         // it finds the first 1 in the matrix representing an uncounted troop
                {
                    ans = max( findans(i,j), ans  );
                    counter++;
                }

            }
        cout<<counter<<" "<<ans<<endl;

    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
int mat[1002][1002],n,m,cnt;

stack<pair<int,int> > st;

bool ok(int x, int y)
{
    if (x>=0 && x<n && y>=0 && y<m) return true;
    return false;
}
void push(int x, int y)
{
    cnt++;
    st.push(make_pair(x,y));
    mat[x][y] = 2;
}
int dfs(int x, int y)
{
    cnt=0;
    push(x,y);
    while (!st.empty())
    {
        pair<int,int> pp = st.top();
        st.pop();
        x = pp.first, y = pp.second;
        if (ok(x-1,y) && mat[x-1][y]==1)
            push(x-1,y);
        if (ok(x-1,y-1) && mat[x-1][y-1]==1)
            push(x-1,y-1);
        if (ok(x,y-1) && mat[x][y-1]==1)
            push(x,y-1);
        if (ok(x+1,y) && mat[x+1][y]==1)
            push(x+1,y);
        if (ok(x+1,y+1) && mat[x+1][y+1]==1)
            push(x+1,y+1);
        if (ok(x,y+1) && mat[x][y+1]==1)
            push(x,y+1);
        if (ok(x-1,y+1) && mat[x-1][y+1]==1)
            push(x-1,y+1);
        if (ok(x+1,y-1) && mat[x+1][y-1]==1)
            push(x+1,y-1);
    }
    
}
void solve()
{
    int i,j;
    cin>>n>>m;
    assert(n>0 && n<=1000);
    assert(m>0 && m<=1000);
    for (i=0; i<n; i++)
        for (j=0; j<m; j++)
            cin>>mat[i][j];
    
    int clusters=0, max_elem=0;
    for (i=0; i<n; i++)
        for (j=0; j<m; j++)
        {
            if (mat[i][j]==1)
            {
                dfs(i,j);
                max_elem = max(max_elem,cnt);
                clusters++;
            }
        }
    cout<<clusters<<" "<<max_elem<<endl;
}
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

coding problems solutions