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


  • 0
    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;
        }
    }
    

Log in to reply
 

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