Clear DFS solution 73 ms. BTW: You can go from 2 to 9 without crossing any number?!


  • 5
    H

    Initially I thought the line from 2 to 9 will go across 5 and 6. However, it's not true.
    I realized this fact after reading others' posts. This is not clarified in the problem.

    Could anyone help me reducing the length of this solution, without making it less clear? I feel like the check() could be optimized a bit..

    public class Solution {
        private int cnt = 0;
        boolean[] visited = new boolean[10];
        public int numberOfPatterns(int m, int n) {
            for (int i = 1; i <= 9; i ++) {
                dfs(i, 1, m, n);
            }
            return cnt;
        }
        private void dfs(int start, int count, int m, int n) {
            if (count >= m) {
                if (count <= n) {
                    cnt++;
                } else {
                    return;
                }
            }
            visited[start] = true;
            for (int i = 1; i <= 9; i ++) {
                if (check(start, i)) {
                    visited[i] = true;
                    dfs(i, count + 1, m, n);
                    visited[i] = false;
                }
            }
            visited[start] = false;
        }
        private boolean check(int n1, int n2) {
            if (visited[n2]) {
                return false;
            }
            int r1 = (n1-1) / 3;
            int r2 = (n2-1) / 3;
            int c1 = (n1-1) % 3;
            int c2 = (n2-1) % 3;
            int smallN = Math.min(n1, n2);
            int colDiff = Math.abs(c1 - c2);
            int rowDiff = Math.abs(r1 - r2);
            if (colDiff == 2) {
                if (rowDiff == 2) {
                    return visited[5];
                } else if (rowDiff == 0) {
                    return visited[smallN + 1]; // check middle col
                }
            } else if (colDiff == 0) {
                if (rowDiff == 2) {
                    return visited[smallN + 3]; // check middle row
                }
            }
            return true;
        }
    }

  • 2
    E

    Really like your idea. Made some improvement to the indexing and logic in the check function.

    For any backtracking problem, the key part is to generate the valid possible next step and the rest is only mechanical work. If you have problem understanding the check function below. Try to visualize the three different scenarios on a paper.

    public class Solution {
    boolean[] visit = new boolean[9];
    int ret = 0;
    public int numberOfPatterns(int m, int n) {
        for(int i = 0; i < 9; i++){
            visit[i] = true;
            helper(i, 1, m, n);
            visit[i] = false;
        }
        return ret;
    }
    private void helper(int node, int k, int m, int n){
        if(k >= m){
            ret++;
            if(k == n) return;
        }
        for(int i = 0; i < 9; i++){
            if(check(node, i)){
                visit[i] = true;
                helper(i, k + 1, m, n);
                visit[i] = false;
            }
        }
    }
    private boolean check(int a, int b){
        if(visit[b]) return false;
        int rowDis = Math.abs(a / 3 - b / 3);
        int colDis = Math.abs(a % 3 - b % 3);
        if(rowDis == 2 && colDis == 2) return visit[4];
        if(rowDis == 2 && colDis == 0) return visit[1 * 3 + a % 3];
        if(rowDis == 0 && colDis == 2) return visit[a / 3 * 3 + 1];
        return true;
    }
    }

  • 0
    H

    The improvement for indexing is great! Thanks!


  • 0
    Y

    Thanks for your answer. But I don't understand why check() works when colDiff == 2 && rowDiff == 1. Suppose we first traverse 1, and the second number is 6 after several loops, would the check() output true which means that 1 to 6 is a correct path?


  • 1
    H

    @yuanjun, the problem is not that clear, but go back to the image in the problem, you need to consider each number as a circle, not a square, so no number come into the way between 1 to 6, or 2 to 9.


  • 1
    Y

    Thanks, I finally realize that 1 to 6 or 2 to 9 can be connected directly in Android Unlock Patterns.


  • 0
    S

    can someone tell me what's wrong with my code?

    class Solution {
    	int[] nexts = {-2, -1, 0, 1, 2};
    
    	public int numberOfPatterns(int m, int n) {
    		int count = 0;
    		boolean[][] visited = new boolean[3][3];
    
    		for(int keys = m; keys <= n; ++keys){
    			for(int i = 0; i < 3; ++i) {
    				for(int j = 0; j < 3; ++j) {
    					visited = new boolean[3][3];
    					count += getPatterns(i, j, 1, keys, visited);
    				}
    			}
    		}
    		return count;
    	}
    
    	public int getPatterns(int i, int j, int curKeys, int keys, boolean[][] visited) {
    		if(i < 0 || j < 0 || i >= 3 || j >= 3 || visited[i][j]) return 0;
    
    		if(curKeys == keys) return 1;
    
    		int count = 0;
    		visited[i][j] = true;
    
    		for(int k = 0; k < 5; ++k) {
    			for(int l = 0; l < 5; ++l) {
    				if((k == 0 && l == 0) || (k == 0 && l == 2) || (k == 2 && l == 0) || (k == 2 && l == 2) || (k == 4 && l == 4) || (k == 4 && l == 2) || (k == 4 && l == 0) || (k == 2 && l == 4) || (k == 0 && l == 4)) continue;
    
    				count += getPatterns(i + nexts[k], j + nexts[l], curKeys + 1, keys, visited);
    			}
    		}
    
    		visited[i][j] = false;
    		return count;
    	}
    

Log in to reply
 

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