Good catch. A function called "markShortestPath" ought to mark the shortest
path, huh?
Don
On Monday, April 21, 2014 4:38:32 PM UTC-4, bujji wrote:
>
>
> Nice solution. good. Looks like in your markShortestPath(int
> i, int i, int d) function
> you missed to set distance[i][j] = d; as first statement.
>
>
>
>
> On Mon, Apr 21, 2014 at 10:01 AM, Don <dond...@gmail.com <javascript:>>wrote:
>
>> 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 algogeeks+...@googlegroups.com <javascript:>.
>>
>
>
--
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 algogeeks+unsubscr...@googlegroups.com.
