This is a problem in a programming contest but I am stuck at it for the past two days

``````void DrowningVillage(int gridSize,int villageHeights[][10],int origin[])
{
int i=0,j,k=0,x=origin[1],y=origin[0],z=0,output1[100],Heights[10][10];
for(i=0;i<gridSize+2;i++)
for(j=0;j<gridSize+2;j++)
Heights[i][j]=1000;    //For removing garbage values and for later comparisons
for(i=0;i<gridSize;i++)
for(j=0;j<gridSize;j++)
Heights[i+1][j+1]=villageHeights[i][j];   //Converting matrix so garbage values do not fall in comparisons
for(i=0;i<100;i++)
output1[i]=1000;
for(j=1;j<=gridSize*gridSize;j++)
{
output1[k++]=Heights[x][y];
output1[k++]=Heights[x-1][y];              //Storing neighbors in output1 array and then comparing them
output1[k++]=Heights[x+1][y];
output1[k++]=Heights[x][y-1];
output1[k++]=Heights[x][y+1];
for(z=j;z<k;z++)                                         //Finding the smallest number
if(output1[z]<=output1[j])
output1[j]=output1[z];
if(output1[j]==Heights[x][y+1])            //changing the origin to smallest number
{
y=y+1;
Heights[x][y-1]=1000;
}
else if(output1[j]==Heights[x][y-1])
{
y=y-1;
Heights[x][y+1]=1000;
}
else if(output1[j]==Heights[x+1][y])
{
x=x+1;
Heights[x-1][y]=100;
}
else if(output1[j]==Heights[x-1][y])
{
Heights[x][y+1]=100;
x=x-1;
}

}
for(i=0;i<gridSize*gridSize;i++)
cout<<output1[i];

}``````

I am getting correct output for the first two elements but after that it only shows the smallest number afterwards present in the array. It would be really helpful if anybody could tell me where is the problem or point me into the right direction .
P.S : I am just a student and I am not cheating or anything. I was just participating for solving puzzles and experience and I am just posting to get a different and probably more experienced perception.

2
Contributors
3
Replies
4
Views
6 Years
Discussion Span
Last Post by alwaysLearning0

Looks like this problem can be solved using Breath first search (BFS) with Priority queue.

you can use min heap to solve this problem.

Keep it simple

example:
2 4 6
7 1 5
3 2 0

``````put Source in the Priority queue
while(priority queue is not empty){
1. top = Take top out of the queue.
2. top is now drowning.
3. Put the adjacent not drowned nodes of the top in the priority queue
}``````

I hope it helps

but how would i convert a 2d array into a binary heap with given root (element at the origin given). I mean every element would have 4 neighbors (excluding the edges) ?

You wouldn't convert the 2d array into the heap, you will still traverse the graph on basis of the 2d array, in heap you will only put the height, and location of the height.

Consider this data structure:

``````class Node{
int height,
int row;
int col;
}``````

you will put this node in to the heap, and heap will construct on basis of the value of the height.
You will still need the 2d array to find out the adjacent nodes.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.