-
use a function to calculate sortest distance to all node, and store in an matrix.
-
using a priority queue: [x, y, distance], PQ is sorted by distance.
-
while:
- pop PQ. in the PQ, there will all different ways to go stored and we choose the closest path to go first.
- don't check if meet the target since there might be a closer road.
- each node go to 4 directions set count to 0 for each direction.
- in each direction, use while loop to go forward until hit wall, and count the steps.
- dont forget to -1 for x and ywhen on the wall
- calculate the new distance.
- if new distance < distanceArray[x][y], update distance array and push it to the PQ. dont care about a larger distance.
-
in main function
- initialize the distance array to maxint
- if distance of distination if still maxint, return -1, otherwise return distance.