Problem Link : http://www.codechef.com/CDCK2015/problems/COUNTC
Author :Ankur Goel
Tester : Ankur Goel
Editorialist : Shuchita Garg
Problem :
A sea contains a number of continents. From a sea, we have randomly picked up an area of Dimensions M * N.
Each continent is represened by 1 or group of 1’s (joined either horizontally or vertically) in this area.
And 0’s represent the water that surrounds those continents. Each unit of this area can contain either 0 or 1
representing continent/part of continent or water surrounding the continent respectively.
For this given area of Dimension M*N Find the Number of continents present in it.
Note: A group of 1’s joined either horizontally or vertically is considered as a single continent.
Explanation:
To solve this Problem, we can apply the backtracking technique. Map the Given problem into a 2-D array, We have find out the Number of groups of 1's. Starting with element at pos(0,0) we traverse the whole matrix. While traversing, if we found that element to be 0, we simply continue,
otherwise, :
we pass the index of that element to a function . And now starting with that element we make a recursive call to its left element, its right element, its up element and with the down element.
And if they are zero, then we simply return, else make them zero.
Now when return to main function, after all the calls to the function passed with index gets over, all the 1's present as a single group in the matrix, will become zero, and then in the main function we increment our count to continent by 1. and the same process continues with the rest elements of the matrix.
Algo :
void make(int **A,int i,int j)
{
if(i<0 || j<0 || i>=m || j>=n)
return;
if(A[i][j]==0)
return;
else
A[i][j]=0;
make(A,i,j+1);
make(A,i,j-1);
make(A,i-1,j);
make(A,i+1,j);
}
main()
{
for: i=1 to m
for j=1 to n
if(a[i][j]==0)
continue;
else
{
count++;
make(a[i][j],i,j);
}
}