bool bad[X][Y];
int distance[X][Y];
void markShortestPath(int i, int i, int d)
{
if ((i >= 0) && (j >= 0) && (i < X) && (j < Y) && (distance[i][j] > d)
&& !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
}
void findShortestPath()
{
int i,j;
for(i = 0; i < X; ++i)
for(j = 0; j < Y; ++j)
distance[i][j] = 1000000000;
markShortestPath(X-1, Y-1, 0);
if (distance[0][0] == 1000000000)
{
printf("No path exists\n");
return;
}
i = j = 0;
printf("Start at (0,0)\n");
while(distance[i][j])
{
if (distance[i+1][j] == distance[i][j]-1) ++i;
else if (distance[i-1][j] == distance[i][j]-1) --i;
else if (distance[i][j+1] == distance[i][j]-1) ++j;
else if (distance[i][j-1] == distance[i][j]-1) --j;
printf("Move to (%d, %d)\n", i,j);
}
}
On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:
>
> Create a matrix distance[x][y] and set all values to a large number.
> This will represent the distance to travel to the destination on the
> shortest route.
> Now set the distance at the destination to zero.
> Set all adjacent locations to one, and repeat the process recursively,
> always setting valid adjacent locations with a larger distance value to the
> distance from the current location plus one. In the end, you will have the
> distance from every location on the grid. Now you can find the shortest
> path from any location by always moving to a space which is closer than
> your current location.
>
> Don
>
> On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:
>>
>> Consider a city whose streets are defined by an X ×Y grid. We are
>> interested in
>> walking from the upper left-hand corner of the grid to the lower
>> right-hand corner.
>> Unfortunately, the city has bad neighborhoods, whose intersections we do
>> not want
>> to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
>> and
>> only if the intersection between streets i and j is in a neighborhood to
>> avoid.
>>
>> Give an O(XY ) algorithm to find the shortest path across the grid that
>> avoids
>> bad neighborhoods. You may assume that all blocks are of equal length.
>> For partial
>> credit, give an O(X^2 Y^2) algorithm.
>>
>> If we walk in down or right directions only Dynamic programming solution
>> would be simple. But because of bad intersection points, we may need to
>> walk in up, down, right or left directions.
>>
>> -Thanks
>> Bujji
>>
>>
>>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
