Java Solution easy to understand


  • 0
    public class Solution {
        int combinations=0;
        public int numberOfPatterns(int m, int n) {
            int [][] memo= new int[3][3];
            int count=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                {
                    memo[i][j]=1;
                    backtrack(memo,n,m,1,i,j);
                    memo[i][j]=0;
                }
            return combinations;
        }
    
        public void backtrack(int[][] memo, int max,int min, int count, int prevX, int prevY)
        {
            if(count>max) return;
            if(count>=min && count<=max) combinations++;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                {
                    if(memo[i][j]!=0) continue;
                    int num= (i-prevX)*(i-prevX)+(j-prevY)*(j-prevY);
                    if(num==5||num==2||num==1||memo[(prevX+i)/2][(prevY+j)/2]==1)
                    {
                           memo[i][j]=1;
                           backtrack(memo,max,min,count+1,i,j);
                           memo[i][j]=0;
                    }
                }
        }
    }
    

    In every step, calculate the distance between current node and previous node.
    utilizing the distance to determine the availability.


Log in to reply
 

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