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


  • 0
    S
    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.


Log in to reply
 

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