C++ DFS


  • 0
    class Solution {
    public:
        int numberOfPatterns(int m, int n) {
            int res = 0;
            int ans;
            vector<bool> visited(10,false);
            vector<vector<int>> jumps(10,vector<int>(10,0));
            jumps[1][3] = jumps[3][1] = 2;
            jumps[4][6] = jumps[6][4] = 5;
            jumps[7][9] = jumps[9][7] = 8;
            jumps[1][7] = jumps[7][1] = 4;
            jumps[2][8] = jumps[8][2] = 5;
            jumps[3][9] = jumps[9][3] = 6;
            jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
            helper(1,1,m,n,res,visited,jumps);
            ans = res*4;
            res = 0;
            helper(2,1,m,n,res,visited,jumps);
            ans += res*4;
            res = 0;
            helper(5,1,m,n,res,visited,jumps);
            ans += res;
            return ans;
        }
        
        void helper(int start,int len, int m, int n, int& res, vector<bool>& visited, vector<vector<int>>& jumps) {
            if(len>=m) res++;
            len++;
            if(len>n) return;
            visited[start] = true;
            for(int i=1;i<=9;i++) {
                if(visited[i]) continue;
                if(jumps[start][i]>0) {
                    if(visited[jumps[start][i]]) {
                        helper(i,len,m,n,res,visited,jumps);
                    }
                } else {
                    helper(i,len,m,n,res,visited,jumps);
                }
            }
            visited[start] = false;
        }
    };
    

Log in to reply
 

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