private int[][] points = new int[][]{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}};

public int numberOfPatterns(int m, int n) {

boolean[][] visited = new boolean[3][3];

// corner

int[] res0 = new int[1];

dfs(visited, 0, 0, m, n, 1, res0);

// edge

int[] res1 = new int[1];

dfs(visited, 0, 1, m, n, 1, res1);

// center

int[] res2 = new int[1];

dfs(visited, 1, 1, m, n, 1, res2);

return res0[0] * 4 + res1[0] * 4 + res2[0];

}

private void dfs(boolean[][] visited, int i, int j, int m, int n, int level, int[] res) {

if (level > n) return;

if (level >= m && level <=n) res[0]++;

visited[i][j] = true;

for (int[] p: points) {

if (!visited[p[0]][p[1]] && canGo(i, j, p[0], p[1], visited)) {

dfs(visited, p[0], p[1], m, n, level+1, res);

}

}

visited[i][j] = false;

}

private boolean canGo(int i1, int j1, int i2, int j2, boolean[][] visited) {

if (!isJumping(i1, j1, i2, j2)) return true;

return visited[(i1+i2)/2][(j1+j2)/2];

}

private boolean isJumping(int i1, int j1, int i2, int j2) {

return (i1 == i2 && Math.abs(j1-j2) == 2) ||

(j1 == j2 && Math.abs(i1-i2) == 2) ||

(Math.abs(i1-i2) == 2 && Math.abs(j1-j2) == 2);

}

public int numberOfPatterns2(int m, int n) {

// Skip array represents number to skip between two pairs

int skip[][] = new int[10][10];

skip[1][3] = skip[3][1] = 2;

skip[1][7] = skip[7][1] = 4;

skip[3][9] = skip[9][3] = 6;

skip[7][9] = skip[9][7] = 8;

skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;

boolean vis[] = new boolean[10];

int rst = 0;

// DFS search each length from m to n

for(int i = m; i <= n; ++i) {

rst += DFS(vis, skip, 1, i - 1) * 4; // 1, 3, 7, 9 are symmetric

rst += DFS(vis, skip, 2, i - 1) * 4; // 2, 4, 6, 8 are symmetric

rst += DFS(vis, skip, 5, i - 1); // 5

}

return rst;

}

// cur: the current position

// remain: the steps remaining

int DFS(boolean vis[], int[][] skip, int cur, int remain) {

if(remain < 0) return 0;

if(remain == 0) return 1;

vis[cur] = true;

int rst = 0;

for(int i = 1; i <= 9; ++i) {

// If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)

if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) {

rst += DFS(vis, skip, i, remain - 1);

}

}

vis[cur] = false;

return rst;

}

public int numberOfPatterns3(int m, int n) {

boolean[][] visited = new boolean[3][3];

int[] res = new int[1];

for (int i=0; i<3; i++) {

for (int j=0; j<3; j++) {

dfs(i, j, visited, m, n, 1, res);

}

}

return res[0];

}

private void dfs(int i, int j, boolean[][] visited, int m, int n, int len, int[] res) {

if (visited[i][j] || len > n) return;

if (len >= m) res[0]++;

visited[i][j] = true;

for (int ii=0; ii<3; ii++) {

int di = Math.abs(i - ii);

for (int jj=0; jj<3; jj++) {

int dj = Math.abs(j - jj);

if (di == 0 && dj == 0) continue;

if ((di == 2 && dj != 1) || (dj == 2 && di != 1)) {

if (!visited[(i+ii)/2][(j+jj)/2]) continue;

}

dfs(ii, jj, visited, m, n, len+1, res);

}

}

visited[i][j] = false;

}