MAZE SOLVER project

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.

EXAMPLE: if you$$re using Dijkstra, there$$s a different implementation $($because there are multiple solutions for this$).$ Please, also indicate the solution $($what e$.$g algorithm you used$).$

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, e$.$g if you approach is Dijkstra.

$--->$ 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 $($THEY$\text{'}$RE SHOWN IN THE SCREENSHOTS ATTACHED$)$

So$,$ the maze$\_11$x$11.$txt:

$-----------------------------------------------------------------------$

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$

$-------------------------$

tHE next one, maze$\_31$x$31.$txt:

$---------------------------------$

G$06$X$5$X$5739507778202$X$8669926$X$587$

$3$X$1$X$7$X$0$XXXXXXX$0$XXXXX$6$XXX$8$XXX$8$X$5$

$2$X$934$X$6$XS$0977$X$005672965$X$17932$X$6$

$7$XXXXX$5$XXXXX$0$XXX$7$XXXXXXX$5$XXXXX$4$

$27635$X$081$X$2$X$958$X$8$X$9$X$595$X$1$X$433$X$3$

XXXX$2$XXX$7$X$1$XXX$1$X$1$X$3$X$0$X$3$XXX$4$X$4$X$2$

$432$X$4495878$X$090$X$565$X$5$X$25196$X$115$

$3$X$5$X$1$XXXXXXX$9$XXXXXXX$1$XXXXXXXXX$6$

$4$X$2$X$709$X$4$X$192$X$73130$X$789$X$95415$X$7$

$0$X$8$XXX$5$X$6$X$9$XXX$9$XXX$5$XXX$1$X$2$XXX$0$X$2$

$1$X$6$X$92690$X$17269$X$4$X$932$X$2$X$734$X$4$X$7$

$1$X$2$XXXXX$0$XXXXXXX$8$XXX$7$X$7$XXX$4$X$4$XX

$6$X$99644$X$8$X$47193$X$213$X$2$X$83349$X$477$

$4$XXXXX$3$X$6$X$8$X$1$X$8$XXX$7$X$9$XXXXXXXXX$4$

$0$X$968$X$3$X$9$X$5$X$8$X$6$X$080$X$65959$X$59913$

$2$XXX$4$X$9$XXX$8$X$6$X$9$X$6$X$2$XXXXX$2$X$3$XXX$5$

$786$X$3$X$75365$X$6$X$909$X$813$X$289$X$996$X$3$

XX$2$X$2$XXXXXXX$2$XXXXXXXXX$5$XXX$9$X$1$X$8$

$5$X$1$X$24193$X$345$X$490$X$88048$X$5$X$0$X$9$X$9$

$4$X$9$X$2$XXXXX$7$XXX$9$X$7$X$1$XXXXX$3$X$6$X$4$XX

$2$X$2$X$609$X$086$X$248$X$019$X$400$X$724$X$223$

$3$X$3$XXX$5$X$7$X$8$X$1$XXXXXXXXX$5$X$0$XXXXX$1$

$8$X$26459$X$6$X$3$X$1$X$635$X$968$X$539$X$79923$

$5$XXXXX$9$X$6$XXX$2$X$2$X$2$X$9$X$7$XXX$8$X$2$XXX$4$

$0$X$04885$X$17886$X$6$X$068$X$099$X$9$X$4$X$828$

$3$X$0$XXXXXXXXXXX$2$XXXXXXX$9$XXX$2$XXX$0$

$732$X$9$X$7723643$X$381$X$638$X$389$X$207$X$8$

$3$XXX$5$X$6$XXXXX$8$X$3$X$7$X$9$X$2$XXX$3$XXX$1$X$3$

$1$X$81966$X$882$X$677$X$3$X$9$X$792$X$62111$X$9$

$6$XXXXXXX$1$X$7$XXXXX$5$X$2$X$1$XXXXXXXXX$1$

$880688547$X$7417695$X$3$X$53218550162$

$--------------------------------------$

There's also the maze$\_101$x$101$ attached in the screenshot. PLEASE, I NEED YOUR HELP TO PROVIDE ME WITH CORRECT ANSWER