Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- int minL, maxL;
- unordered_map<int, unordered_map<int, int>> passingThrough;
- public :
- bool isPermissible(int prevNum, int currNum, vector<bool> &visited){
- int a = min(prevNum, currNum);
- int b = max(prevNum, currNum);
- if(passingThrough[a][b]==-1){
- //i.e no number is on the line crossing and b
- return true;
- }
- return visited[passingThrough[a][b]];
- }
- //returns number of combinations, we're currently on cth number
- int h_numberOfPatterns(int c, int prevNum, vector<bool> &visited){
- if(c == maxL + 1){
- return 0;
- }
- int answer = 0;
- for(int i=1; i<=9; i++){
- if(!visited[i] && isPermissible(prevNum, i, visited)){
- if(minL <= c){
- answer += 1;
- }
- visited[i] = true;
- answer += h_numberOfPatterns(c+1, i, visited);
- visited[i] = false;
- }
- }
- return answer;
- }
- int numberOfPatterns( int m, int n) {
- minL = m;
- maxL = n;
- passingThrough[1][2] = -1;
- passingThrough[1][3] = 2;
- passingThrough[1][4] = -1;
- passingThrough[1][5] = -1;
- passingThrough[1][6] = -1;
- passingThrough[1][7] = 4;
- passingThrough[1][8] = -1;
- passingThrough[1][9] = 5;
- passingThrough[2][3] = -1;
- passingThrough[2][4] = -1;
- passingThrough[2][5] = -1;
- passingThrough[2][6] = -1;
- passingThrough[2][7] = -1;
- passingThrough[2][8] = 5;
- passingThrough[2][9] = -1;
- passingThrough[3][4] = -1;
- passingThrough[3][5] = -1;
- passingThrough[3][6] = -1;
- passingThrough[3][7] = 5;
- passingThrough[3][8] = -1;
- passingThrough[3][9] = 6;
- passingThrough[4][5] = -1;
- passingThrough[4][6] = 5;
- passingThrough[4][7] = -1;
- passingThrough[4][8] = -1;
- passingThrough[4][9] = -1;
- passingThrough[5][6] = -1;
- passingThrough[5][7] = -1;
- passingThrough[5][8] = -1;
- passingThrough[5][9] = -1;
- passingThrough[6][7] = -1;
- passingThrough[6][8] = -1;
- passingThrough[6][9] = -1;
- passingThrough[7][8] = -1;
- passingThrough[7][9] = 8;
- passingThrough[8][9] = -1;
- vector<bool> visited(10, false);
- int answer = 0;
- for(int num=1; num<=9; num++){
- if(minL <= 1){
- answer += 1;
- }
- visited[num] = true;
- answer += h_numberOfPatterns(2, num, visited);
- visited[num] = false;
- }
- return answer;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement