java dfs solution


  • 0
    2
    public class Solution {
        private int[][] invalid = {{1, 3, 2}, {4, 6, 5}, {7, 9, 8}, {1, 7, 4}, {2, 8, 5}, {3, 9, 6}, {1, 9, 5}, {3, 7, 5}};
        private int m;
        private int n;
        private boolean[] visited;
        
        public int numberOfPatterns(int m, int n) {
            this.m = m;
            this.n = n;
            visited = new boolean[10];
            return 4 * dfs(1, 1) + 4 * dfs(2, 1) + dfs(5, 1);
        }
        private int dfs(int i, int l) {
            visited[i] = true;
            int ret = 0;
            if (l >= m) ret++;
            if (l == n) {
                visited[i] = false;
                return ret;
            }
            for (int j = 1; j <= 9; j++) {
                if (!visited[j]) {
                    boolean skip = false;
                    for (int[] inv : invalid) {
                        if (Math.min(i, j) == inv[0] && Math.max(i, j) == inv[1] && !visited[inv[2]]) {
                            skip = true;
                            break;
                        }
                    }
                    if (!skip) {
                        ret += dfs(j, l + 1);
                    }
                }
            }
            visited[i] = false;
            return ret;
        }
    }
    

Log in to reply
 

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