Short C++ solution


  • 11
    class Solution {
    public:
        int numberOfPatterns(int m, int n) {
            return count(m, n, 0, 1, 1, 1, 1);
        }
    private:
        int count(int m, int n, int used, int i1, int j1, int i2, int j2) {
            int number = m <= 0;
            if (!n) return 1;
            for (int i=0; i<3; i++) {
                for (int j=0; j<3; j++) {
                    int I = i2 + i, J = j2 + j, used2 = used | (1 << (i*3 + j));
                    if (used2 > used && (I % 2 || J % 2 || used2 & (1 << (I/2*3 + J/2))))
                        number += count(m-1, n-1, used2, i2, j2, i, j);
                }
            }
            return number;
        }
    };
    

    used is the 9-bit bitmask telling which keys have already been used and (i1,j1) and (i2,j2) are the previous two key coordinates. A step is valid if...

    • I % 2: It goes to a neighbor row or
    • J % 2: It goes to a neighbor column or
    • used2 & (1 << (I/2*3 + J/2))): The key in the middle of the step has already been used.

  • 0
    F

    This seems to be a very elegant solution. Could you share your thoughts on how you come up with this solution? What does i1, j2, i2, j2 stand for? Why do you need to consider whether used2 > used or not?


  • 0
    C

    Can you explain more on these lines? Thanks

    int I = i2 + i, J = j2 + j, used2 = used | (1 << (i3 + j));
    if (used2 > used && (I % 2 || J % 2 || used2 & (1 << (I/2
    3 + J/2))))
    number += count(m-1, n-1, used2, i2, j2, i, j);


  • 1

    (i2,j2) are the coordinates of the previous key, (i,j) are the coordinates of the new key. So the new line goes from (i2,j2) to (i,j). The middle point of the line is at ((i2+i)/2, (j2+j)/2). My I and J are those middle coordinates, except I didn't divide by 2 yet, so I can stay in integers.

    Now if I % 2 isn't zero, then that means I/2 and thus (i2+i)/2 is no integer. Which means the middle point of the line is not a key. Same with the other coordinate. If both those checks fail, then the middle point of the new line is a key, and thus I need to check that that key has been used already.


  • 3
    B

    Hi, it seems that i1 and j1 are not necessary since you just need previous i and j.
    And thank you for sharing this great solution!!!


  • 0
    C
    This post is deleted!

  • 0
    E

    @StefanPochmann

    This is a very concise solution.

    In the output "return count(m, n, 0, 1, 1, 1, 1);" the function count doesn't have to be called with (1,1,1,1) as (i1, i2, i3, i4). Even if it called 'count(m, n, 0, a, b, c, d) with all of (a, b, c, d) being anything betwee 0 and 2 each, e.g. count(m, n, 0, 2, 3, 2, 3) it'd still be the right answer.
    Correct?

    Can you also comment on the complexity of this? It seems like if there are X elements in the pattern, the complexity is O( (X^n) * X) = O(X^(n+1))
    ( X^n refers to X next steps from any given point and that's done n times. Multiplied by X because the beginning point can be any of X elements).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.