# C++ DFS

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

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