Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int dfs(vector<bool> &vis, vector<vector<int>> &skip, int cur, int remain) {
- if(remain < 0) return 0;
- if(remain == 0) return 1;
- vis[cur] = true;
- int rst = 0;
- for(int i = 1; i <= 9; ++i){
- // If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)
- if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))){
- rst += dfs(vis, skip, i, remain - 1);
- }
- }
- vis[cur] = false;
- return rst;
- }
- int numberOfPatterns(int m, int n) {
- // Skip array represents number to skip between two pairs
- vector<vector<int>> skip(10, vector<int>(10, 0));
- skip[1][3] = skip[3][1] = 2;
- skip[1][7] = skip[7][1] = 4;
- skip[3][9] = skip[9][3] = 6;
- skip[7][9] = skip[9][7] = 8;
- skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
- vector<bool> vis(10, false);
- // DFS search each length from m to n
- int rst = 0;
- for(int i = m; i <= n; ++i) {
- rst += dfs(vis, skip, 1, i - 1) * 4; // 1, 3, 7, 9 are symmetric
- rst += dfs(vis, skip, 2, i - 1) * 4; // 2, 4, 6, 8 are symmetric
- rst += dfs(vis, skip, 5, i - 1); // 5
- }
- return rst;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement