MAZE SOLVER project $($use A search $*$ or another approach; Dijkstra must NOT be used$)$

Description: You are placed in a maze with a starting point S$.$

Your need to find your way to goal G AS QUICKLY$($as few cells$/$moves as possible$)$ AS POSSIBLE and collect some coins on the way.

Walls are X$,$ each cell in a passage has some coins $0$ to $9.$ So if you have an X $-->$ no passage.

Moves are $1$ unit each.

You are ALLOWED TO MOVE DIAGONALLY

Outside maze is lava. $($just like a wall; you can$$t go there $).$

Write a program $($PROVIDE SINGLE$/$MULTIPLE FILES$)$ in Python to read text files and solve the maze.

VERY IMPORTANT NOTE!!!!! $===>$You are allowed to use A search$*,$ which combines Dijkstra$$s algorithm with a heuristic to improve efficiency. Please, because Dijkstra is NOT allowed for this project.

OTHER EXPLANATIONS!! PLEASE, ALSO READ:

In this project:

$--->$ For the $11$x$11$ maze $($Mazes$\_$to$\_$be$\_$read... file$),$ you can simply CHECK YOUR ANSWER that you receive by the code output through doing it in a piece of paper. That means your algorithmic approach may be correct $($again use A search$*)$

$--->$ For the other TWO mazes, it is going to take very long to do it in paper, so just MAKE SURE THE ALGORITHMIC APPROACH GIVES THE RIGHT ANSWER, SO LOGIC IS CORRECT.

$--->$Find S$,$ and the path.

$---->$ ALSO VERY IMPORTANT: There may be $2$ ways to reach the goal BUT find $1$ that gets you out the QUICKEST!!!!!!!

$---->$ E$.$g $8$ and $6$ may be valid solutions, but not ideal $($you skip the corners$)...$

ALSO SUBMIT:

$1.$ Also, besides everything I said above, submit solutions to all $3$ mazes as text. $($single row separated by comma for example $533,1984,9000)$

$2.$ In text also provide time and space complexity of your solution. Common algorithms might have different implementations and different complexities.

Solution should be sum of coins collected on the way out of maze!!!!!!!!!!

If there are multiple solutions with same number of moves, I want to see the solution with LEAST coins collected $($as I said earlier$).$

EXAMPLE:

So$,$ this is the maze. You have to get up at the left corner G $(7$x$7$ maze$)$

Diagonal moves $-->1$ unit each $($so NOT Eucleadean, so NOT sqrt$(2)).$

You$$re trying to get out of the maze as soon as possible.

G$503746$

$0$XXXXX$4$

$3$XS$6138$

$3$XXXXXX

$1$X$19736$

$5$XXXXX$8$

$3375042$

Solution is $6+1+3+($we skip $8$ since we move diagonally$)+4+($we skip $6$ since we move diagonally$)+4+7+3+0+5==33.$ The answer in this example is $33!!!$ FOR THIS CASE.

NOW THAT YOU UNDERSTOOD THE LOGIC BY AN EXAMPLE, THE ONLY FILES THAT YOU SHOULD TAKE IN CONSIDERATION FOR THIS PROJECT ARE:

maze$\_11$x$11.$txt

maze$\_31$x$31.$txt

maze$\_101$x$101.$txt

Again, please do NOT use Dijskra, but A search $*$ instead. G$95$X$823$X$101$

$4$X$1$X$7$X$2$X$0$X$8$

$6$X$237$X$569$X$2$

$0xxxxxxxxx0$

$6$X$858$X$41707$

$2$X$5$XXX$1$XXXX

$7$X$3$X$525$XS$68$

$4$X$7$X$9$XXXXX$6$

$5$X$4$X$6$X$33242$

$5$X$8$X$3$X$9$XXXX

$100$X$8096058$ OTHER FILES ARE REPRESENTED IN THE SCREENSHOTS