# Mobile Pattern Lock.

Last Updated: 17 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Example :

``````We can treat the 3*3 grid as follows:-
``````

``````4-7-9-6 is an invalid pattern lock because while joining 7-9 it passes through key 8 which has not been previously selected in pattern.
9-1-2-3 is an invalid pattern lock because while joining 9-1 it passes through key 5 which has not been previously selected in pattern.
4-2-6-8 is a valid pattern lock.
``````

##### Input Format :
``````The first line contains a single integer ‘T’ representing the number of test cases.

The only line of each test case contains two space-separated integers ‘M’ and ‘N’ representing two integers for which you need to return the total number of valid patterns.
``````
##### Output Format :
``````For each test case print an integer denoting the total number of valid mobile pattern locks which consist of at least ‘M’ keys and at most ‘N’ keys.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= M <= N <= 9

Time Limit: 1sec
``````

## Approach 1

We can do DFS from all the starting points. We can easily observe 1,3,7, and 9 can be treated as the same i.e. the number of patterns for each one of them would be the same due to symmetry. Similarly, 2,4,6, and 8 will have the same number of patterns as a starting point. We can apply DFS as follows:

• We will declare an array/list vis which stores if the key was visited. Initially, all are initialized ‘false’.
• To avoid invalid moves we will maintain a 2-D array ‘point[10][10]’ where ‘point[i][j]’ stores the index of the key in between line joining ‘i’ and ‘j’. If there are no points store it as 0.
• Declare ‘ans’ and initialize it with zero.
• Iterate over all path lengths from ‘m’ to ‘n’. For each length we will calculate as follows:-
• We will write a recursive function  ‘int traverse(int currKey, int movesLeft, bool vis[10])’ where ‘currKey’ is key which we are at present and ‘movesLeft’ is the number of moves we are yet to make. We will implement the function as follows:-
• If ‘movesLeft’ is zero we have come to the end of a valid pattern lock so we return 1.
• We will mark ‘currKey’ visited i.e. ‘vis[currKey] = true’.
• Declare ‘numberOfPaths’ and initialize it with zero.
• We will iterate over all the keys. If ‘i-th’ key is not visited yet and either no key is present between ‘currKey’ and ‘i-th’ key or if the key is present it has already been visited. Then we can visit ‘i-th’ key next into our path. Therefore we call function recursively ‘numberOfPaths’ += ‘traverse(i, movesLeft-1, vis)’.
• After iterating over all the keys mark ‘currKey’ as not visited i.e. ‘vis[currKey] = false’.
• Return ‘numberOfPaths’.
• We will now use the above recursive function:-
• ‘ans’ += 4* ‘traverse(1, i-1, vis)’ , because 1,3,7, and 9 are similar.
• ‘ans’ += 4* ‘traverse(2, i-1, vis)’ , because 2,4,6, and 8 are similar.
• ‘ans’ += ‘traverse(5, i-1, vis)’.
• Return ‘ans’