1. you can use backtracking to find your way through a [login to view URL] a rectangular maze that you divide into squares, with certain squares colored to indicate the walls of the maze. Thus the maze can be represented as a two dimensional array. Using backtracking, write a program to find ypor way through a maze. you may want to use the following definitions: //c++ const int WIDTH=10; const int HEIGHT=10; enum square{Empty,Wall,Visited} //example maze variable square Maze[WIDTH][HEIGHT] The input for this program will be series of integers,one for each square,with 0 representing EMPTY and 1 representing a Wall(see example below). Assume that you can move only in four directions(not diagonally) and that you cannot move beyond the borders of the array(eg. at position 0,0 you cannot move up or left). Further assume that the start of the maze is always the upper-left corner(position 0,0) and the finish is always the lower-right corner(position WIDTH-1,HEIGHT-1).At the end you should display the maze and the path you have [login to view URL] input & output for a 10*10 maze. Input: 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 output: ------------ |S+++ ++ | |OOO+ + + | |++OOO + +| |+ ++O+++ | |+OO++++ | |+++O++OOO | |++OOOOO+O+ | | +++ ++O+| |+ + + ++O+| |+ + OF| |------------ + wall O path S start F finish
## Deliverables
C++ program to solve the above problem
## Platform
windows