Given a grid with obstacles, we want to find the path that gets you to the end in the shortest amount of time, using dijkstra’s algorithm. in this grid, you can move in all 8 directions: up, down, left, right, and the 4 diagonals.

you have been working out, and you can climb over obstacles, but it takes you longer.
moving to a grid location without an obstacle takes 1 minute. moving to a grid location
with an obstacle takes 2 minutes.
input
• the first line contains an integer, n, the dimension of the nxn grid.
• the second line contains two space-separated integers, the starting position in the
order row column.
• the third line contains two space-separated integers, the ending position in the order
row column.
• the next n lines contain the space separated row. each element is either a o indicating
no obstacle or a x indicating an obstacle.
constraints
you can assume a path exists (and therefore that the starting and ending positions are os)
and that the starting and ending positions are in-bounds.