static int N;
static boolean[][] lattice;
static final long func(int remainSteps, int lastX, int lastY) {
    long count = 0;

    int nextX = lastX-1;
    if (nextX >= 0 && !lattice[nextX][lastY]) {
        if (remainSteps == 1) {
            count++;
        } else {
            lattice[nextX][lastY] = true;
            count += func(remainSteps-1, nextX, lastY);
            lattice[nextX][lastY] = false;
        }
    }

    nextX = lastX+1;
    if (nextX <= N && !lattice[nextX][lastY]) {
        if (remainSteps == 1) {
            count++;
        } else {
            lattice[nextX][lastY] = true;
            count += func(remainSteps-1, nextX, lastY);
            lattice[nextX][lastY] = false;
        }
    }

    int nextY = lastY-1;
    if (nextY >= 0 && !lattice[lastX][nextY]) {
        if (remainSteps == 1) {
            count++;
        } else {
            lattice[lastX][nextY] = true;
            count += func(remainSteps-1, lastX, nextY);
            lattice[lastX][nextY] = false;
        }
    }

    nextY = lastY+1;
    if (nextY <= N && !lattice[lastX][nextY]) {
        if (remainSteps == 1) {
            count++;
        } else {
            lattice[lastX][nextY] = true;
            count += func(remainSteps-1, lastX, nextY);
            lattice[lastX][nextY] = false;
        }
    }
    return count;
}

//调用的时候
for (int n = 2; n <= 25; n++) {
    N = n;
    lattice = new boolean[N+1][N+1];
    lattice[0][0] = true;
    lattice[1][0] = true;
    long nPaths = func(n-1, 1, 0);
}