IPS Round:

Questions:

Given a screen pattern lock of 'n' rows and 'm' columns. Determine the number of distinct patterns a screen pattern lock has.

Conditions:

• Each dot can only be touched once.
• You are only allowed to connect vertically/horizontally adjacent dots.

For example, if there are 9 dots on the screen labelled as:

1 2 3 4 5 6 7 8 9

The possible patterns can be: 1 1 -> 2 4 -> 7 -> 8 -> 5 -> 6 -> 3 5 -> 8 etc.

Sample Input:

2 2

Sample Output:

28

Explanation:

There are 7 patterns starting from dot 1. Due to symmetry, the total answer is 7 * 4 = 28:

1 1 -> 2 1 -> 3 1 -> 2 -> 4 1 -> 3 -> 4 1 -> 2 -> 4 -> 3 1 -> 3 -> 4 -> 2

About approach and time/space complexities.