# Java DP&DFS solution, straight forward but looks stupid....

• ``````public class Solution {
int count;
public int numberOfPatterns(int m, int n) {
if(m > n) return 0;

int[] res = new int[n + 1];
res[0] = 0;
res[1] = 9;

for(int k = 2; k <= n; k ++){
count = 0;
boolean[][] visited = new boolean[3][3];

for(int i = 0; i < 3; i ++){
for(int j = 0; j < 3; j ++){
dfs(i, j, visited, k);
}
}
res[k] = res[k - 1] + count;
}
return m == 0 ? res[n] : res[n] - res[m - 1];
}
private void dfs(int i, int j, boolean[][] visited, int k){
if(i < 0 || i >= 3 || j < 0 || j >= 3) return ;
if(visited[i][j]) return ;
if(k == 1 && !visited[i][j]){
count ++;
return ;
}

visited[i][j] = true;
dfs(i + 1, j, visited, k - 1);
dfs(i - 1, j, visited, k - 1);
dfs(i, j + 1, visited, k - 1);
dfs(i, j - 1, visited, k - 1);
dfs(i + 1, j + 1, visited, k - 1);
dfs(i - 1, j - 1, visited, k - 1);
dfs(i - 1, j + 1, visited, k - 1);
dfs(i + 1, j - 1, visited, k - 1);

dfs(i + 1, j + 2, visited, k - 1);
dfs(i + 1, j - 2, visited, k - 1);
dfs(i + 2, j + 1, visited, k - 1);
dfs(i + 2, j - 1, visited, k - 1);
dfs(i - 1, j + 2, visited, k - 1);
dfs(i - 1, j - 2, visited, k - 1);
dfs(i - 2, j + 1, visited, k - 1);
dfs(i - 2, j - 1, visited, k - 1);

if(i - 1 >= 0 && j - 1 >= 0 && visited[i - 1][j - 1])
dfs(i - 2, j - 2, visited, k - 1);
if(i - 1 >= 0 && j >= 0 && visited[i - 1][j])
dfs(i - 2, j, visited, k - 1);
if(i - 1 >= 0 && j + 1 < 3 && visited[i - 1][j + 1])
dfs(i - 2, j + 2, visited, k - 1);
if(j + 1 < 3 && visited[i][j + 1])
dfs(i, j + 2, visited, k - 1);
if(i + 1 < 3 && j + 1 < 3 && visited[i + 1][j + 1])
dfs(i + 2, j + 2, visited, k - 1);
if(i + 1 < 3 && visited[i + 1][j])
dfs(i + 2, j, visited, k - 1);
if(i + 1 < 3 && j - 1 >= 0 && visited[i + 1][j - 1])
dfs(i + 2, j - 2, visited, k - 1);
if(j - 1 >= 0 && visited[i][j - 1])
dfs(i, j - 2, visited, k - 1);

visited[i][j] = false;

// return count;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.