graph search algorithm - BFS
According to the problem description, you have to find the shortest path between two points in a grid, 'S' & 'E'.
data structures :
triple = a structure with 3 elements( x, y, length ), 'length' is the length of the last jump that has entered this cell
grid[301][301] = an array of strings with size of more than 300 for input grid
mark[301][301][4] = a 3d array to mark and save the distance from the start cell in a jump with size of 1, 2 or 3
After I get input, I find the position of the start and end point, then set all the members of mark to -1, and then create a queue of 'triple', push start to queue and set it's length to 1, because the next jump I can do from this point is a jump with length 1.
Then in a while loop I retrieve the last triple that I have pushed to queue and continue jumping from this point to the neighbor points, before I push the new triple into the queue, I set the length of it to "1 + the current triple's length" to save that how I can continue jumping from this point.
What you have to be careful of is that you can't jump through obstacles, for example assume that you can make jumps with size of 3 at this level. S.#E but you can't reach from 'S' to 'E', so check whether there are any obstacles in your jump or not.
At the end check mark[end.first][end.second][1,2,3], any of them that is not -1 and is the smallest one is the answer otherwise the answer is 'NO'.
What will be the value of mark[start.first][start.second][1] , mark[start.first][start.second][2] ,mark[start.first][start.second][3] ? And how are we sure that if I make visit to one co-ordinate x,y with jump 1,we will not have the shortest path by visiting it from another point with jump 1 from your algorithm?
ReplyDelete