Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Oliver and the battle problem solution

YASH PAL, 31 July 2024
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

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

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes