City Tour

There are A cities numbered from 1 to A. You have already visited M cities, the indices of which are given in an array B of M integers.

If a city with index i is visited, you can visit either the city with index i-1 (i >= 2) or the city with index i+1 (i < A)if they are not already visited.
Eg: if N = 5 and array M consists of [3, 4], then in the first level of moves, you can either visit 2 or 5.

You keep visiting cities in this fashion until all the cities are not visited.
Find the number of ways in which you can visit all the cities modulo 10^9+7.

Input Format

```The 1st argument given is an integer A, i.e total number of cities.
The 2nd argument given is an integer array B, where B[i] denotes ith city you already visited.
```
Output Format

```Return an Integer X % (1e9 + 7), number of ways in which you can visit all the cities.
```
Constraints

```1 <= A <= 1000
1 <= M <= A
1 <= B[i] <= A
```
For Example

```Input:
A = 5
B = [2, 5]
Output:
6

Explanation:
All possible ways to visit remaining cities are :
1. 1 -> 3 -> 4
2. 1 -> 4 -> 3
3. 3 -> 1 -> 4
4. 3 -> 4 -> 1
5. 4 -> 1 -> 3
6. 4 -> 3 -> 1
```
See Expected Output

思路

BFS

Solution:

Time: O(A^A)
Space: O(A)

public class Solution {
public int solve(int A, ArrayList<Integer> B) {
int[] count = new int[]{0};
helper(A, B, count);
return count[0];
}

private void helper(int A, ArrayList<Integer> B, int[] count) {
if (A == B.size()) {
System.out.println(B.toString());
count[0] += 1;
return;
}
Set<Integer> exist = new HashSet<>(B);
Set<Integer> candidates = new HashSet<>();
for (int i = 0; i < B.size(); i ++) {
int curr = B.get(i);
if (curr - 1 >= 1 && !exist.contains(curr - 1)) {
}
if (curr + 1 <= A && !exist.contains(curr + 1)) {
}
}
for (int candidate : candidates) {
ArrayList<Integer> b = new ArrayList<>(B);
helper(A, b, count);
}
}
}

思路2

1,2
4,6
8,10
1，2和8，10这样两边的城市分别只有一种visit的办法，2 -> 1，8 -> 9 -> 10
4，6这样中间的城市则有2^(size - 1)的方法，因为可以从两边visit，比如4，6有2^2 = 4种方法，分别是456，465，654，645。

[<1,2>, <4,6>, <8,10>]
1 * 1 * (2C2) = 1
1 * 4 * (5C3) = 40
40 * 1 * (8C3) = 2240
2240

Solution:

Time: O(A^2)
Space: O(A^2)

```public class Solution {
public static class Group {
int x;
int y;

public Group(int x, int y) {
this.x = x;
this.y = y;
}

public String toString() {
return "<" + this.x + "," + this.y + ">";
}
}

public int solve(int A, ArrayList<Integer> B) {
long[][] combinations = getCombs(A);
long[] binomials = getBinomials(A);
long total = 1;
int totalCity = 0;
List<Group> groups = getGroups(A, B);
// System.out.println(groups.toString());

for (int i = 0; i < groups.size(); i ++) {
long possibilityInGroup = 1;
Group group = groups.get(i);
int size = group.y - group.x + 1;
totalCity += size;
if (group.x != 1 && group.y != A) {
possibilityInGroup = binomials[size - 1];
}
//System.out.println(total + " * " + possibilityInGroup + " * (" + totalCity + "C" + size + ")");
total = (total * possibilityInGroup) % 1000000007;
total = (total * combinations[totalCity][size]) % 1000000007;
}
return (int) (total % 1000000007);
}

private long[][] getCombs(int A) {
long[][] combs = new long[A + 1][A + 1];
for (int i = 1; i <= A; i ++) {
for (int j = 0; j <= i; j ++) {
if (j == 0 || i == j) {
combs[i][j] = 1;
} else {
// if A is picked, the rest possibilty is N-1 C j - 1
// if A is not picked, the rest is N - 1 C j
combs[i][j] = (combs[i - 1][j] + combs[i - 1][j - 1]) % 1000000007;
}
}
}
return combs;
}

private long[] getBinomials(int A) {
long[] bino = new long[A + 1];
bino[0] = 1;
for (int i = 1; i <= A; i ++) {
bino[i] = (bino[i - 1] * 2) % 1000000007;
}
return bino;
}

private List<Group> getGroups(int A, ArrayList<Integer> B) {
Collections.sort(B);
List<Group> groups = new ArrayList<>();
int next = 1;
for (int i = 0; i < B.size(); i ++) {
int curr = B.get(i);
if (curr - 1 >= next) {