Please Solve Using Java and Recursion !!!

R04: 1D Maze You are given an array of length N and a jump size M. Each element of the array is either 0 or 1. A 0 indicates a location we can be at and a 1 indicates a location we cannot occupy. Hence, you can only move to a location in the array which contains a 0. You start at the 0th index which will always have a 0. For each move you can do one of the following Move one step forward Move one step backward Jump exactly M spaces forward. The new position must contain a 0. You may also move to any position N 1 (outside the array). However, you may not move backward from position 0. If you can move to any position greater than N 1 you have escaped the maze. Write a recursive method that returns true if you can escape otherwise return false. Example Input Expected Output [0, 1, 0, 0, 1] with jump = 2 true [0, 1, 1, 0, 1] with jump = 2 false [0, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 false [0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1] with jump = 3 true This problem is different than the problems weve seen so far because it is not a linear problem. This is known as a decision problem and a backtracking problem. We need to decide for our current location, get a new location, and determine if that helps solve the problem. If it does not then we need to go back to a previous location and try a different decision. This sounds hard but this type of problem is perfect for recursion because the stack instances created by the recursive calls will hold our previous locations. Furthermore, for each call if one decision doesnt work we can move on to the next one by simply make a different call. Before we get to the base cases lets explore what we are being asked to do with some of the examples. The order in which we perform the actions will be the same as the list above. If one decision fails then we move to the next for a given location. If we return to a position we continue with the next decision (we dont restart). Lets look at an example run of the first input. [0, 1, 0, 0, 1], jump = 2 ^ player We try to move forward but we cant. We try to move backward but we cant from position 0. We can jump 2.

[0, 1, 0, 0, 1], jump = 2 ^ player From our new position we can move forward [0, 1, 0, 0, 1], jump = 2 ^ player From this position, we cannot move forward. We can move backward.... but if we do, we end up in a loop. (Try it) The key is that we need to keep track of where weve been, so we dont do any more calculations on that spot. You can think of this like leaving cookie crumbs in an actual maze. Suppose we leave a 1 where weve been before making a move. [0, 1, 0, 0, 1], jump = 2 ^ idx = 0 Place a 1 at our current location. Maze becomes [1, 1, 0, 0, 1] We cant move forward. We cant move backward from index 0. We can jump. [1, 1, 0, 0, 1], jump = 2 ^ idx = 2 Place a 1 at our current location. Maze becomes [1, 1, 1, 0, 1] We can move forward. [1, 1, 1, 0, 1], jump = 2 ^ idx = 3 Place a 1 at our current location. Maze becomes [1, 1, 1, 1, 1] We cant move forward. We cant move backward (because weve already been there) We can jump [1, 1, 1, 1, 1] ^ idx = 5 We passed N 1 so we are out of the maze. This will return true.

Try this with the rest of the mazes to convince yourself. Just note that if you go back to a previous location, while it has a 1 because you set a crumb there, you can still try the other choices. I have provided one more breakdown for the 3rd maze after the pseudocode. Now that we understand the problem and the details all that is needed is to determine the base case, or in this case, base cases and the recursive calls. If you read the description carefully, you can see we are given all of the base cases for this problem. If we make it out of the maze, we return true. If we move onto a location which is not allowed we return false. Thats pretty much it. Next, the recursive case is just the encoding of all of the decisions we need to make. The recursive case will be to either move forward 1 space, move backward 1 space, or to jump M spaces. How can we make these decisions? Well, we either increase or decrease the index by that much. For instance, isSolvableMaze(maze, idx + 1, jump) will move forward. The recursive cases should be setup up in a way to handle out of bounds issues such as trying to go backwards from the 0th position or moving out of the maze. All that is left is to combine these decisions and determine whether we can escape or not. Let me give you a sentence that should help with that. Either we move forward 1 space or we move backward 1 space or we jump M spaces. Is there any words in that sentence that gives you a hint as to how to combine the decisions? Remember that the recursive calls return a Boolean. If you thought that we should OR the return values of make the decisions then you would be correct. This makes not just logical sense but physical sense as you cannot move forward and backward at the same time as would be implied by a logical AND. So now we have enough to write the pseudocode. Boolean isSolvable1DMaze(maze, idx, jump) { If(we made it out) { Return true; } If(we are at a bad location) { Return false; } Place a bread crumb at our current location. Return move forward? || move backward? || jump?; }

3rd Maze [0, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 0 Place a 1 at current location. Maze becomes [1, 1, 0, 0, 0, 1, 1, 0, 1] Cant move forward. Cant move backward from 0th position. Can Jump. [1, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 2 Place 1 at current location. Maze becomes [1, 1, 1, 0, 0, 1, 1, 0, 1] Can move forward. [1, 1, 1, 0, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 3 Place 1 at current location. Maze becomes [1, 1, 1, 1, 0, 1, 1, 0, 1] Can move forward. [1, 1, 1, 1, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 4 Place 1 at current location. Maze becomes [1, 1, 1, 1, 1, 1, 1, 0, 1] Cant move forward. Cant move backward. Cant jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^ idx = 3

Move forward failed. Cant move backward. Cant jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^ idx = 2 Move forward failed. Cant move backward. Cant jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^ idx = 0 Jump failed and that was our last decision. We return false because we cannot escape this maze. No trace necessary for this problem.