Java - Modified BackTracking


  • 0

    Original article - https://leetcode.com/articles/android-unlock-patterns/

    public class Solution {
        public int numberOfPatterns(int m, int n) {
            if (n == 0 || m > n) return 0; 
            boolean[] used = new boolean[9]; 
            int[] res = new int[1]; 
            backTrack(used, m, n, -1, 0, res); 
            return res[0]; 
        }
        public void backTrack(boolean[] used, int low, int hi, int pre, int len, int[] res){
            if (len > hi) return; 
            if (len >= low) res[0]++; 
            
            for (int i = 0; i < 9; i++)
                if (isValid(used, pre, i)) {
                    used[i] = true; 
                    backTrack(used, low, hi, i, len + 1, res); 
                    used[i] = false; 
                }
        }
        
        public boolean isValid (boolean[] used, int pre, int cur) {
            if (pre == -1) return true; 
            if (used[cur]) return false; 
            if ((pre + cur) % 2 == 1) return true; //adjacent move + knight move
            int mid = (pre + cur) / 2; 
            if (mid == 4) return used[4]; //diagonal corner to corner move
            if (pre % 3 != cur % 3 && pre / 3 != cur / 3) // one step diagonal move 
                return true; 
            return used[mid]; //same row/column corner to corner jump
        }
        
    }

Log in to reply
 

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