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

• 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;
}
}``````

• 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;
}
}``````

• The improvement for indexing is great! Thanks!

• 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?

• @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.

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

• 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;
}
``````

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