# JAVA....7ms beats 100%

• using symmetry to greatly reduce the calculation

``````public class Solution {
int m,n,sum;
int[][] canPassBy;
public int numberOfPatterns(int m, int n) {
this.m=m;
this.n=n;
sum=0;
if (m<=1 && 1<=n) sum+=9;
if (n<2) return sum;
canPassBy= new int[10][10];
canPassBy[1][3]=canPassBy[3][1]=2;
canPassBy[1][7]=canPassBy[7][1]=4;
canPassBy[3][9]=canPassBy[9][3]=6;
canPassBy[7][9]=canPassBy[9][7]=8;
canPassBy[1][9]=canPassBy[9][1]=canPassBy[3][7]=canPassBy[7][3]=5;
canPassBy[2][8]=canPassBy[8][2]=canPassBy[4][6]=canPassBy[6][4]=5;
boolean[] filled = new boolean[10];
filled[0]=true;
initStep2(filled, 1, 2, 8);
initStep2(filled, 2, 1, 8);
initStep2(filled, 1, 5, 4);
initStep2(filled, 5, 1, 4);
initStep2(filled, 2, 5, 4);
initStep2(filled, 5, 2, 4);
initStep2(filled, 2, 4, 8);
initStep2(filled, 1, 8, 8);
initStep2(filled, 2, 7, 8);
return sum;
}
private void initStep2(boolean[] filled, int num1, int num2, int multiplier){
filled[num1] = true;
move(filled, 2, num2, multiplier);
filled[num1] = false;
}
private void move(boolean[] filled, int step, int index, int multiplier){
if (step>=m) sum+=multiplier;
if (step<n) {
filled[index] = true;
for (int i=1; i<10; i++) {
if (!filled[i] && filled[canPassBy[index][i]]) {
move(filled, step+1, i, multiplier);
}
}
filled[index] = false;
}
}
}
``````

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