351. Android Unlock Patterns

class Solution {
    public int numberOfPatterns(int m, int n) {
        for(int i = m; i <= n; i++)
        {
            // for each length
            for(int j = 0; j < 9; j++)
            {
                used = 1 << j;
                dfs(i, 1, j);
            }
        }
        return re;
    }

    void dfs(int cap, int count, int cur)
    {
        if(count == cap)
        {
            re++;
            return;
        }
        int row = cur / 3, col = cur % 3;
        for(int i = 0; i < 9; i++)
        {
            if((used & (1 << i)) != 0) continue;
            int nr = i / 3, nc = i % 3, dr = nr - row, dc = nc - col,
            adr = Math.abs(dr), adc = Math.abs(dc);
            if(adr == 0 && adc == 2 || adr == 2 && adc == 0 ||
                adr == 2 && adc == 2)
            {
                int mrow = dr / 2 + row, mcol = dc / 2 + col,
                mid = mrow * 3 + mcol;
                if((used & (1 << mid)) == 0) continue;
            }
            used |= 1 << i;
            dfs(cap, count + 1, i);
            used &= ~(1 << i);
        }
    }

    int re = 0, used = 0;
}