Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The efficient algorithm needs to be done and proved for the best solution for the given problem:

User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination Coordinates of each of the individual Z paths.

Given: (#) Each path comprises of the cells which are ADJACENT to each other and NOT diagonal. (#) Time taken to cross each cell is EQUAL and is an unit time. (#) Travelling starts from the respective source coordinates of each path in the grid SIMULTANEOUSLY. (#) Paths may intersect, BUT after say 'x'th unit time no two paths must intersect in one particular cell at a time. If such case arises, then one of the paths need to bypass into a new path taking alternate adjacent cell just before the clashing cell.

Output: Z no. of paths which are SHORTEST possible without clash.

[Say there are two paths (Z=2), say X to Y and W to Z. While travelling, both X and W start simultaneously from their respective source coordinates, going to their respective destinations Y and Z such that they should take the SHORTEST possible path, AND after 'x'th unit time, they must not CLASH (when both the paths have traveled exactly (x-1) no. of cells and clashing into the 'x'th cell) into one single cell. If that happens, one of the path needs to be bypassed towards its destination keeping in mind without clash, shortest possible path. And this has to be implemented for Z no. of lines starting simultaneously in the grid.]

P.S.- Yes, I should have mentioned it clearly. I mean the total of all the path lengths must be as less as possible. And, since I'm a new user, I wasn't allowed to use any image. Please check the image link as follows so that you can get an idea about the clash thing as how it is supposed to happen:

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.