C solution, 16ms, Accepted as best.


  • 0
    F
    void helper(int key, int flag, int *val, int m, int n, int level, int *res) {
        if (level >= m) *res += 1;
        if (level == n) return;
        int i, r = key / 3, c = key % 3;
        for (i = 0; i < 9; i++) {
            if (!(flag & val[i])) {
                int rr = i / 3;
                int cc = i % 3;
                if ((r + rr) % 2 || (c + cc) % 2) {
                    helper(i, flag | val[i], val, m, n, level + 1, res);
                    continue;
                }
                int mr = (r + rr) / 2;
                int mc = (c + cc) / 2;
                if (!(flag & val[mr * 3 + mc])) continue;
                helper(i, flag | val[i], val, m, n, level + 1, res);
            }
        }
    }
    int numberOfPatterns(int m, int n) {
        int res = 0, flag, tmp; 
        int val[9] = {1, 2, 4, 8, 16, 32, 64, 128, 256};
        
        flag = val[0];
        tmp = 0;
        helper(0, flag, val, m, n, 1, &tmp);
        res += 4 * tmp;
        
        flag = val[1];
        tmp = 0;
        helper(1, flag, val, m, n, 1, &tmp);
        res += 4 * tmp;
        
        flag = val[4];
        tmp = 0;
        helper(4, flag, val, m, n, 1, &tmp);
        res += tmp;
        
        return res;
    }

Log in to reply
 

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