Hi Don,
At most we can reach a point from 4 adjacent points. So, time
complexity will be O(XY) only.
-Thanks,
Bujji.
On Mon, Apr 21, 2014 at 1:38 PM, bujji jajala <[email protected]> wrote:
> 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].
