Hi Don,
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.
It looks like time complexity of this program is greater than O(XY). It
depends on number of multiple paths
to a point with different path lengths and order of evaluation of
paths.Evaluating recursion paths from greater
run length to smaller run lengths will result in updating distance[i][j]
several times.
Any improvements can we think of to improve this to achieve O(XY) bound?
-Thanks
Bujji.
On Mon, Apr 21, 2014 at 10:01 AM, Don <[email protected]> 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 [email protected].
>
--
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].
