Java solution, 60+ ms


  • 1
    B
    public int numberOfPatterns(int m, int n) {
        boolean[][] visited = new boolean[3][3];
        int ret = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                ret += backtracking(m, n, visited, i, j, 0);
            }
        }
        return ret;
    }
    
    private int backtracking(int m, int n, boolean[][] visited, int y, int x, int cur) {
        visited[y][x] = true;
        cur++;
        int count = 0;
        if (cur >= m && cur <= n) {
            count++;
        }
        if (cur == n) {
            visited[y][x] = false;
            return count;
        }
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == y && j == x) { continue; }
                if (visited[i][j]) { continue; }
                int dx = j - x;
                int dy = i - y;
                /* neighbors */
                if ((Math.abs(dx) <= 1 && Math.abs(dy) <= 1)
                /* not in the same line */
                || (x != j && y != i // same row or col
                    && y - x != i - j // l2r, high
                    && x - y != j - i // l2r, low
                    && x + y != j + i) // r2l
                /* same line but not neighbors */
                || visited[y + dy/2][x + dx/2]) {
                    count += backtracking(m, n, visited, i, j, cur);
                }
            }
        }
        visited[y][x] = false;
        return count;
    }

Log in to reply
 

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