Concise Java, DFS + Memoization + Bits (11ms)


  • 0
    S
    public int numberOfPatterns(int m, int n) {
        if (n == 0 || m > n) return 0;
    
        int[] memoiz = new int[262144];
    
        int c = 0;
        for (int i = 0; i < 9; i++)
            c += count(m, n, i, 1 << i, 1, memoiz);
    
        return c;
    }
    
    private int count(int m, int n, int from, int selected, int selectedCount, int[] memoiz) {
        if (selectedCount == n) return 1;
    
        int hash = selected + (1 << (from + 9));
        if (memoiz[hash] > 0) return memoiz[hash];
    
        // >= m is a valid move too, so include them
        int count = selectedCount >= m ? 1 : 0;
    
        for (int to : NEAR[from]) {
            if ((selected & (1 << to)) == 0)
                count += count(m, n, to, selected | (1 << to), selectedCount + 1, memoiz);
        }
    
        for (int to[] : FAR[from]) {
            if ((selected & (1 << to[0])) > 0 && (selected & (1 << to[1])) == 0)
                count += count(m, n, to[1], selected | (1 << to[1]), selectedCount + 1, memoiz);
        }
    
        return memoiz[hash] = count;
    }
    
    final int NEAR[][] = {
            {1, 4, 3, 5, 7}, // 0
            {0, 2, 3, 4, 5, 6, 8}, // 1
            {1, 4, 5, 3, 7}, // 2
            {0, 1, 4, 7, 6, 2, 8}, // 3
            {0, 1, 2, 3, 5, 6, 7, 8}, // 4
            {2, 1, 4, 7, 8, 0, 6}, // 5
            {3, 4, 7, 1, 5}, // 6
            {6, 3, 4, 5, 8, 0, 2}, // 7
            {7, 4, 5, 3, 1} // 8
    };
    
    final int FAR[][][] = {
            {{1, 2}, {4, 8}, {3, 6}}, // 0
            {{4, 7}}, // 1
            {{1, 0}, {4, 6}, {5, 8}}, // 2
            {{4, 5}}, // 3
            {}, // 4
            {{4, 3}}, // 5
            {{3, 0}, {4, 2}, {7, 8}}, // 6
            {{4, 1}}, // 7
            {{7, 6}, {4, 0}, {5, 2}}, // 8
    };

Log in to reply
 

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