BFS might be faster, though. Don On Tuesday, April 22, 2014 1:11:00 AM UTC-4, bujji wrote: > > 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]<javascript:> > > 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] <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 [email protected] <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 [email protected].
