JAVA....7ms beats 100%


  • 0
    D

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

Log in to reply
 

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