Integer Grid Reachable Problem
Given a one or two dimensional space. At first you are at the zero point. You can only go to another integer grid point in the space and the step you can make is limited by some conditions. Then, it is asked that if you can reach a target point in the space.
This kind of problems concerns about some common mathematics knowledge. At first let us start from a simple one dimension instance.
Move on a line
Let's say at first you are at zero point on the like. A set lengths of moves is given and you can only move by a distance in that set. You can move in both directions. Now you are asked if you can reach a target position .
At first let's consider we can move by distances of and . Assume and are coprimes, then we have a proposition that we can always find and so that . This is according to extended Euclidean algorithm. Also we can easily find that if and are not coprime. That is where means the greatest common divisor. So we have and where and are coprime. Then we obviously can get , subject to Both and can be get by extended Euclidean algorithm. But there are still a stronger identity gives that for any and if we have then we must have is a multiple of . The identity is named Bézout's identity.
With this identity, the problem is easy to solve as it is in fact equivalent to asked if there exists integer solution , for equation . More generally, if we have more possible steps , the equation has integer solutions if and only if is divisible by .
Move on a plane
In two dimensional case, the problem is a little more complex. The move is usually limited by pairs of move in two dimension: . Assume the set given conforms to the following two properties:
- If in the set, then must also in the set.
- If in the set, then , and must also in the set.
As for such an instance of problem, we have some simpler solution. We can consider the reachability subject to two dimensions respectively. Let's pick dimension for instance.
At first, we can start from to if we first go to then we go by and thus get to that point for any . Then, let to be the greatest common divisor of all , then we can prove that we can get to when is divisible by . That is we can find integer solutions of and if we make use of aforementioned identity we get and the greatest common divisor of is obviously . So .
So given a target point , it is reachable if and only if both and is divisible by and .
If one of is odd, then we can get a more strong conclution that we can also reach instead of . because of is odd, we can conclude either or is odd. Assume is odd. Then must be even. Then we go to first, then as is even, we can go from that point by once a time until we meet . Consider all are reachable, thus we can reach now.
So the solution for this problem is:
- For our target point is we do not need to move, so it is reachable.
- If either or can not be divided by it can not be reached.
- If there is one is odd. Then any other than the former two cases is reachable.
- At last, if is even, we can reach it.
The fourth is because, we can always find a solution so that . We use these on corresponding and will get . Thus we can always get to . If is even, obviously we can get to then and the same to so is always reachable. If is odd, we can get to directly.
So, if is even, we can get:
- Both and are even. So we can get to directly.
- Both and are odd. In this case we can get to first and make a move of to get to .