351. Android Unlock Patterns

I was trying to naive DFS to search up to 8 neighbors for each number on pad. But I realized that such way has some issues. First of all, the valid pattern includes [1]-[8] where 8 is not a direct neighbor for 1. Also [1]-[2]-[1]-[4] is a valid pattern for m = 3 which complicates the usage of visited matrix. The top rated solution has a very clever way by using a skip matrix to solve the problem. In the dfs function, it just checks from 1 to 9 to see if they are next to each other or the number between them has been visited before so that they becomes next again.

1:  class Solution {  
2:  public:  
3:    int numberOfPatterns(int m, int n) {  
4:      vector<vector<int>> skip(10, vector<int>(10, 0));  
5:      skip[1][3] = skip[3][1] = 2;  
6:      skip[1][7] = skip[7][1] = 4;  
7:      skip[3][9] = skip[9][3] = 6;  
8:      skip[7][9] = skip[9][7] = 8;  
9:      skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = 5;  
10:      int res = 0;  
11:      vector<bool> visited(10, 0);  
12:      for (int l = m; l <= n; l++) {  
13:        res += dfs(1, skip, visited, l-1) * 4;  
14:        res += dfs(2, skip, visited, l-1) * 4;  
15:        res += dfs(5, skip, visited, l-1);  
16:      }  
17:      return res;  
18:    }  
19:    int dfs(int n, vector<vector<int>> &skip, vector<bool> &visited, int l) {  
20:      if (l == 0) return 1;  
21:      int res = 0;  
22:      visited[n] = true;  
23:      for (int i = 1; i <= 9; i++) {  
24:        if (!visited[i] && (skip[n][i] == 0 || visited[skip[n][i]])) {  
25:          res += dfs(i, skip, visited, l-1);  
26:        }  
27:      }  
28:      visited[n] = false;  
29:      return res;  
30:    }  
31:  };