package question;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question403 {
 public static void main(String[] args) {
 System.out.println(new Question403().canCross(new int[]{
 0,1,3,5,6,8,12,17
 }));
 }

 public boolean canCross(int[] stones) {
 ArrayList<Integer>[] arr = new ArrayList[stones.length];
 for (int i = 0; i < arr.length; i++) {
 arr[i] = new ArrayList<>();
 }
 arr[0].add(0);
 for (int i = 0; i < stones.length; i++) {
 for (int j = i + 1; j < stones.length; j++) {
 for (Integer num : arr[i]) {
 if (Math.abs(num - (stones[j] - stones[i])) <= 1) {
 arr[j].add(stones[j] - stones[i]);
 break;
 }
 }
 }
 }
 return !arr[stones.length - 1].isEmpty();
 }

 public boolean canCross2(int[] stones) {
 Set<Integer>[] arr = new Set[stones.length];
 for (int i = 0; i < arr.length; i++) {
 arr[i] = new HashSet<>();
 }
 arr[0].add(1);
 for (int i = 0; i < stones.length; i++) {
 for (int j = i + 1; j < stones.length; j++) {
 int x = stones[j] - stones[i];
 if (arr[i].contains(x)) {
 arr[j].add(x);
 arr[j].add(x-1);
 arr[j].add(x+1);
 }
 }
 }
 return !arr[stones.length - 1].isEmpty();
 }
}