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 <[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].
