C# DFS solution in 157 ms with explanation


  • 1
    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.