C# solution with explanation


  • 0
    A

    The idea is to not continue searching under these conditions:

    1. the next key is on the same row and two columns away, but the key in the middle has been visited;
    2. the next key is on the same column but two rows away, but the key in the middle has been visited;
    3. the next key is across the diagonal, but center key (1,1) has been visited;

    public class Solution 
    {
        public int NumberOfPatterns(int m, int n)
        {
            int res = 0;
            bool[,] visited = new bool[3, 3];
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    res += Search(i, j, m, n, visited);
                }
            }
    
            return res;
        }
    
        private int Search(int i, int j, int m, int n, bool[,] visited)
        {
            if (visited[i, j])
            {
                return 0;
            }
    
            if (--n == 0)
            {
                return 1;
            }
    
            int res = 0;
            if (--m <= 0)
            {
                res = 1;
            }
    
            visited[i, j] = true;
    
            for (int x = 0; x < 3; x++)
            {
                for (int y = 0; y < 3; y++)
                {
                    if (!((x == i && Math.Abs(y - j) == 2 && !visited[i, 1]) || (y == j && Math.Abs(x - i) == 2 && !visited[1, j]) || (Math.Abs(x - i) == 2 && Math.Abs(y - j) == 2 && !visited[1, 1])))
                    {
                        res += Search(x, y, m, n, visited);
                    }
                }
            }
    
            visited[i, j] = false;
            return res;
        }
    }

Log in to reply
 

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