Drowning Village Problem - Output not right

[ag_17]

This is a problem in a programming contest but I am stuck at it for the past two days
Here is a link to the problem : http://www.techgig.com/codecontest_detail.php?type=advanced

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]

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

you can use min heap to solve this problem.

http://en.wikipedia.org/wiki/Binary_heap

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]

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.