**Using c++ to implement the Dijkstra’salgorithm!**

Given a grid with obstacles, we want to find the path that getsyou to the end in the shortest amount of time, using Dijkstra’salgorithm. 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, butit 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 nxngrid.

• The second line contains two space-separated integers, thestarting position in the

order row column.

• The third line contains two space-separated integers, the endingposition in the order

row column.

• The next n lines contain the space separated row. Each element iseither a O indicating

no obstacle or a X indicating an obstacle.

Constraints

You can assume a path exists (and therefore that the starting andending positions are Os)

and that the starting and ending positions are in-bounds.

**Sample Input 0**

40 23 1X X O XX X O OX X X OX O O O

**Sample Output 0**

4

**Sample Input 1**

6 0 15 2O O O O O XX X O X O OO O X O O XX O O O O OO O X X X OX O O X O O

**Sample Output 1**

5

**Sample Input 2**

40 02 0O O O OX X O OO X X OO O O O

**Sample Output 2**

3

**Sample Input 3**

83 36 6O O O O O O O OO O O O O O O OO O O O O O O OO O O O O O O OO O O O O O O OO O O O O O O OO O O O O O O OO O O O O O O O

**Sample Output 3**

3

## Expert Answer

Answer to Using c++ to implement the Dijkstra’s algorithm! Given a grid with obstacles, we want to find the path that gets you t…