20 lines, easy understand backtracking with explanations


  • 0
    A

    At the first glance, the description seems long and complicated. Actually, it can be simplified as:

    • Connect two opposite corners, center should be already visited, such as 1-->9

    • Connect two not-next-to-each-other cells vertically or horizontally, the in-between cell should be already visited. such as 4--->6

    • Any cell not visited can be connected to.

       | 1 | 2 | 3 |
       | 4 | 5 | 6 |
       | 7 | 8 | 9 |
      

    The 9 cells can be divided into 3 groups: A(corner), B(middle), C(Center). We only need to calc once for each group.

    | A | B | A |
    | B | C | B |
    | A | B | A |
    

    The code is a straightforward backtracking approach in C#,

    public class Solution 
    {
        public int NumberOfPatterns(int m, int n) 
        {
            int[,] screen = new int[3,3];
            
            int corner = 0, center = 0, middle = 0;
            NumberOfPatternsUtil(screen, m, n, 0, 0, 1, ref corner);
            NumberOfPatternsUtil(screen, m, n, 1, 1, 1, ref center);
            NumberOfPatternsUtil(screen, m, n, 0, 1, 1, ref middle);
    
            return (corner + middle) * 4 + center;
        }
    
        private void NumberOfPatternsUtil(int[,] screen, int m, int n, int x, int y, int keySequence, ref int result)
        {
            if(keySequence > n) return;
            if(keySequence >= m && keySequence <= n) result ++;
            
            screen[x,y] = keySequence;
            for(int i = 0; i < 3; i++)
            {
                for(int j = 0; j < 3; j++)
                {
                    if(screen[i,j] == 0)
                    {
                        if(Math.Abs(x - i) == 2 && Math.Abs(y - j) == 2 && screen[1,1] == 0)continue;
                        if(x == i && Math.Abs(y - j) == 2 && screen[x, 1] == 0) continue;
                        if(y == j && Math.Abs(x - i) == 2 && screen[1, y] == 0) continue;
    
                        NumberOfPatternsUtil(screen, m, n, i, j, keySequence + 1, ref result);
                    }
                }
            }
            screen[x,y] = 0; //backtracking
        }
    }

Log in to reply
 

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