### Step Numbers题号：178 难度： 55 中英对照

Consider the number 45656.
It can be seen that each pair of consecutive digits of 45656 has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from 0 to 9 at least once.
How many pandigital step numbers less than 1040 are there?

### Code

import java.util.Arrays;

public final class p178 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {
final int Limit=40;
long[][][][] a = new long[Limit][2][2][10];
Arrays.fill(a[0][0][0], 1);
Arrays.fill(a[0][0][1], 0);
Arrays.fill(a[0][1][0], 0);
Arrays.fill(a[0][1][1], 0);
a[0][0][0][0] = 0;
a[0][0][0][9] = 0;
a[0][0][1][9] = 1;

for (int n = 1; n < Limit; n++) {
for (int digit = 0; digit < 10; digit++) {
if (digit == 0) {
a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
} else if (digit == 1) {
a[n][1][0][digit - 1] += a[n - 1][0][0][digit];
a[n][0][0][digit + 1] += a[n - 1][0][0][digit];
a[n][1][1][digit - 1] += a[n - 1][0][1][digit];
a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
} else if (digit == 8) {
a[n][0][0][digit - 1] += a[n - 1][0][0][digit];
a[n][0][1][digit + 1] += a[n - 1][0][0][digit];
a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
a[n][1][1][digit + 1] += a[n - 1][1][0][digit];
a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
} else if (digit == 9) {
a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
} else {
a[n][0][0][digit - 1] += a[n - 1][0][0][digit];
a[n][0][0][digit + 1] += a[n - 1][0][0][digit];
a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
}
}
}

long result = 0;
for (int n = 0; n < Limit; n++) {
for (int digit = 0; digit < 10; digit++) {
result = result + a[n][1][1][digit];
}
}
return ""+result;
}
}
126461847755
0ms