Python: Implement a grid-maze solving program that usesdepth-first search to solve grids. The agent’s actions are movingin one of four directions: up, down, left, and right.
A grid is formatted like below where 1’s represent locations theagent cannot traverse:
1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 0 0 1 0 1
1 0 1 0 0 1 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
The final path can be displayed with ‘S’ for the initial state,‘G’ for the goal state, and ‘*’ symbols for the path:
1 1 1 1 1 1 1 1
1 S 0 0 1 1 1 1
1 * * * 0 0 0 1
1 1 1 * 0 1 0 1
1 0 1 * G 1 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
