33ms 33 lines Java DFS backtracking solution


  • 0
    K
    public class Solution {
        int count = 0;
        public int numberOfPatterns(int m, int n) {
            dfs(m, n, new boolean[3][3], -1, -1, 0);
            return count;
        }
        
        private void dfs(int m, int n, boolean[][] used, int lastX, int lastY, int length) {
            if (length >= m) {
                count++;
            }
            
            if (length == n) {
                return;
            }
            
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (!used[i][j] && (length == 0 || isValid(used, lastX, lastY, i, j))) {
                        used[i][j] = true;
                        dfs(m, n, used, i, j, length+1);
                        used[i][j] = false; 
                    }
                }
            }
        }
        
        private boolean isValid(boolean[][] used, int lastX, int lastY, int currX, int currY) {
            int xDiff = Math.abs(lastX-currX), yDiff = Math.abs(lastY-currY);
            int maxDiff = Math.max(xDiff, yDiff), minDiff = Math.min(xDiff, yDiff);
            return (maxDiff != 2 || minDiff == 1) || used[(lastX+currX) / 2][(lastY+currY) / 2];
        }
    }
    

Log in to reply
 

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