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