pm
BAN USERWell ... looks likes the question says the boundaries are unknown and also we do not have methods to find if we have reached the edge of the grid, which means for all practical purposes we can assume the grid to be infinite.
Now lets look at how the person can reach the apple. The only way I can think of is if he starts moving by covering the immediate cells around him and then go to the next immediate cells. Since this is an rectangular grid it makes sense to cover all the cells around the cell the person is in, then move to the outer cells forming another square and so on spiraling out until he gets the apple, that is a TRUE is returned for the found( ) method for each move.
so if,
R = moveRight( )
L = moveLeft( )
U = moveUp( )
D = moveDown( )
and F = found( )
To search for the immediate cells that form the first square should look like something like this,
R D LL UU RR
Then moving on to the next outer square
R DDD LLLL UUUU RRRR
then the next outer square
R DDDDD LLLLLL UUUUUU RRRRRR
so on ...
So the program would look something like
while(!found())
{
int d = 1; // initializing the number of down movements to 1
int lur = 2; /// initializing the number of left up and right movements to 2
moveRight(); // Moving to the outer square
if(found())
break;
for(int i=0; i<d ;i+=) // moving along the right edge of the square
{
moveDown();
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=) // moving along the bottom edge of the square
{
moveLeft();
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=)
{
moveUp(); // moving along the left edge of the square
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=)
{
moveDown(); // moving along the top edge of the square
if(found())
break;
}
if(found())
break;
d += 2;
lur += 2;
}
#include<stdio.h>
#include<stdlib>
#include<String.h>
struct node
{
char* data;
struct node* next;
};
int totalNumOfChars;
int numOfComps = 1;
int totalNumOfCompsRequired = 0;
int len;
int curIndex = 0;
struct node* ptr;
int recursive(struct node* node)
{
int i;
int isPal = 1;
if(node->next != NULL)
{
isPal = recursive(node->next);
}
if(isPal == 1)
{
for(i=strlen(node->data)-1; i>=0 ; i--)
{
if(node->data[i] == ptr->data[curIndex])
{
numOfComps++;
curIndex++;
if(curIndex >=len)
{
curIndex = 0;
ptr = ptr->next;
len = strlen(ptr->data);
}
}
else
{
return 0;
}
if(numOfComps >= totalNumOfCompsRequired)
{
return 1 & isPal;
}
}
return 1 & isPal;
}
return 0;
}
void main()
{
int isPal = 0;
struct node* head;
struct node* first = malloc(sizeof(struct node));
struct node* second = malloc(sizeof(struct node));
struct node* third = malloc(sizeof(struct node));
first->next = second;
second->next = third;
third->next = NULL;
first->data = "abcc";
second->data = "dcc";
third->data = "ba";
totalNumOfChars = 9;
totalNumOfCompsRequired = totalNumOfChars/2;
ptr = first;
head = first;
len = strlen(head->data);
isPal = recursive(first);
printf("\n\n\tIs palindrom = %d", isPal);
}
I think this will work, the heap could be very big, but at any given time it will be accurate.
So each node has the number of times an element is searched for, as the key. Every time a data element comes in the corresponding node is incremented and the heap nodes with highest number of searches is always at the top and is continually updated.
It would be easier if you can place the link of the 'other questions' here
- pm March 11, 2015