# My Java Solution. DFS with min, max step. Do not known where wrong.

• ``````public class Solution {
private static final int[] DIR = {0, -1, 1, -2, 2};
public int numberOfPatterns(int m, int n) {
int patternCount= 0;

patternCount += 4 * routeCount(0, 0, 1, m, n,new boolean[3][3]) + 4 * routeCount(0, 1, 1, m, n, new boolean[3][3]) + routeCount(1, 1, 1, m, n, new boolean[3][3]);

return patternCount;
}

private int routeCount(int x, int y, int count, int min, int max, boolean[][] map){
int patternCount = 0;

if(count == max){
return 1;
}else{
if(count >= min){
patternCount ++;
}
//for every possible next node, mark and call routeCount
int nextX = x, nextY = y;
for(int i = 0; i < DIR.length; i++){
for(int j = 0; j < DIR.length; j++){
if(DIR[i] == 0 && (DIR[j] == 0 || Math.abs(DIR[j]) == 2)){
continue;
}
if(Math.abs(DIR[i]) == 2 && (Math.abs(DIR[j]) == 2 || DIR[j] == 0)){
continue;
}
nextX = x + DIR[i];
nextY = x + DIR[j];

if(nextX >= 0 && nextX < map.length && nextY >= 0 && nextY < map[nextX].length && !map[nextX][nextY]){
map[nextX][nextY] = true;
patternCount += routeCount(nextX, nextY, count + 1, min, max, map);
map[nextX][nextY] = false;
}
}
}

}

return patternCount;
}
``````

}

// this solution return 48 when 2;2. I don't knwon where wrong. I think my general ideal is right.

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