We can solve the problem by dfs and we need some data structure to store the mid key between two keys. the popular one is 2-D array like mid[1][3] = 2, mid[1][7] = 4, etc. But the problem is that I didn't see any solution which considered mid[1][6] or mid[1][8], etc. All solution treated them as if they were adjacent. Then I tested m=2,n=2 by using the solution in OJ, the answer was 56. @elmirap

How could you get 56 unlock patterns when you are just using two keys **(No jumps through non selected key is allowed**)? If you know, pls show me. ;)

As far as I know, the answer should be 40 not 56. So I wonder if the solution in OJ even is wrong.

keys | patterns (started from that key)

1 2 3 | 3 5 3

4 5 6 | 5 8 5

7 8 9 | 3 5 3