ag_17

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.

alwaysLearning0 39

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

ag_17

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) ?

alwaysLearning0 39

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.