Can anyone please help me understand this code? This code is used to solve this problem. You are playing a game on your cellphone. You are given an array of length n, indexed from 0 to n−1. Each element of the array is either 0 or 1. You can only move to an index which contains 0. At first you are at the 0th position. In each move you can do one of the following things:
Walk one step forward or backward. Make a jump of exactly length m forward. That means you can move from position x to x+1, x−1 or x+m in one move. The new position must contain 0. Also you can move to any position greater than n-1.
You can't move backward from position 0. If you move to any position greater than n−1, you win the game.
Given the array and the length of the jump, you need to determine if it's possible to win the game or not.
n = sc.nextInt();
m = sc.nextInt();
field = new int[n];
for (int i = 0; i < n; i++) {
field[i] = sc.nextInt();
}
if (makeMove(0, new LinkedList<Integer>()))
System.out.println("YES");
else
System.out.println("NO");
. . .
private boolean makeMove(int position, List<Integer> prevPositions)
{
if (prevPositions.contains(position))
return false;
prevPositions.add(position);
if (position < 0) return false;
else if (position >= n) return true;
else if (field[position] == 1) return false;
else {
return makeMove(position + m, prevPositions) ||
makeMove(position + 1, prevPositions) ||
makeMove(position - 1, prevPositions);
}
}
input: 6 2
0 0 0 1 0 0
Output: Yes
input: 6 2
0 0 1 1 0 0
Output: No
So, I am assuming that you understand the concept of recursion, which is calling a method within itself, if not you may want to look it up.
The first section of code is very simple. It initializes the move length m and the array of length n and populates it with random binary digits.
The makeMove method goes through a few base cases to see if a branch of recursion has failed or succeeded.
1.) if (prevPositions.contains(position)) return false; prevPositions.add(position);
After making a move, this code checks whether you have already gotten to this position. If you have, it returns false because this case has already been known to be false, otherwise the method would have already returned true.
2.) if (position < 0) return false; else if (position >= n) return true; else if (field[position] == 1) return false;
-You can't have a negative position, so that returns false. -If your position is greater than n then you win, so return true -You can't move to a position that contains a non-zero digit, so return false
3.) return makeMove(position + m, prevPositions) || makeMove(position + 1, prevPositions) || makeMove(position - 1, prevPositions);
This code makes recursive calls to other moves from possible positions and returns true if any of these calls are true. Since you can leap to position+m, then it makes sense that if makeMove(position+m, prevPositions) is true, then makeMove(position, prevPositions) is also true. Similarly you can move to position+1 and position-1 so calls to makeMove of these positions should return the same value as makeMove of your original position. Hope this made sense!
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments