SHARE
TWEET

Untitled

a guest Oct 2nd, 2015 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  4.  
  5. public class Snake
  6. {
  7.     private static List<char> snake = new List<char>();
  8.     private static int snakeSize = 0;
  9.     private static int snakesFound = 0;
  10.     private static HashSet<string> uniqueSnakes = new HashSet<string>();
  11.  
  12.     public static void Main()
  13.     {
  14.         int n = int.Parse(Console.ReadLine());
  15.  
  16.         char[,] matrix = new char[n * 2, n * 2];
  17.  
  18.         for (int i = 0; i < n * 2; i++)
  19.         {
  20.             for (int j = 0; j < n * 2; j++)
  21.             {
  22.                 matrix[i, j] = ' ';
  23.             }
  24.         }
  25.  
  26.         FindSnakes(n, n, 'S', matrix);
  27.  
  28.         Console.WriteLine("Snakes count = {0}", snakesFound);
  29.     }
  30.  
  31.     private static void FindSnakes(int row, int col, char direction, char[,] matrix)
  32.     {
  33.         if (snakeSize >= matrix.GetLength(0))
  34.         {
  35.             return;
  36.         }
  37.         if ((col < 0) || (row < 0) || (col >= matrix.GetLength(1)) || (row >= matrix.GetLength(0)))
  38.         {
  39.             return;
  40.         }
  41.  
  42.         if (matrix[row, col] != ' ')
  43.         {
  44.             return;
  45.         }
  46.  
  47.         snakeSize++;
  48.  
  49.         if (snakeSize == matrix.GetLength(1) / 2)
  50.         {
  51.             snake.Add(direction);
  52.  
  53.             if (!SnakeAlreadyExists(string.Join("", snake)))
  54.             {
  55.                 snakesFound++;
  56.                 Console.WriteLine(string.Join("", snake));
  57.             }
  58.  
  59.             snakeSize--;
  60.             snake.RemoveAt(snake.Count - 1);
  61.  
  62.             return;
  63.         }
  64.  
  65.         snake.Add(direction);
  66.         matrix[row, col] = 'X';
  67.  
  68.         FindSnakes(row, col + 1, 'R', matrix);
  69.  
  70.         if (snakeSize > 1)
  71.         {
  72.             FindSnakes(row + 1, col, 'D', matrix);
  73.         }
  74.         if (snakeSize > 2)
  75.         {
  76.             FindSnakes(row, col - 1, 'L', matrix);
  77.         }
  78.         if (snakeSize > 3)
  79.         {
  80.             FindSnakes(row - 1, col, 'U', matrix);
  81.         }
  82.         matrix[row, col] = ' ';
  83.         snake.RemoveAt(snake.Count - 1);
  84.         snakeSize--;
  85.     }
  86.     private static bool SnakeAlreadyExists(string snake)
  87.     {
  88.         var reversedSnake = ReverseFlow(snake);
  89.  
  90.         while (reversedSnake[1] != 'R')
  91.         {
  92.             reversedSnake = Rotate(reversedSnake);
  93.         }
  94.  
  95.         if (uniqueSnakes.Contains(reversedSnake))
  96.         {
  97.             return true;
  98.         }
  99.  
  100.         reversedSnake = GetVerticalMirrorImage(reversedSnake);
  101.  
  102.         if (uniqueSnakes.Contains(reversedSnake))
  103.         {
  104.             return true;
  105.         }
  106.  
  107.         reversedSnake = ReverseFlow(reversedSnake);
  108.  
  109.         while (reversedSnake[1] != 'R')
  110.         {
  111.             reversedSnake = Rotate(reversedSnake);
  112.         }
  113.  
  114.         if (uniqueSnakes.Contains(reversedSnake))
  115.         {
  116.             return true;
  117.         }
  118.  
  119.         uniqueSnakes.Add(snake);
  120.         return false;
  121.     }
  122.  
  123.     private static string GetVerticalMirrorImage(string snake)
  124.     {
  125.         var newSnake = new StringBuilder();
  126.         var newDirection = ' ';
  127.  
  128.         for (int i = 0; i < snake.Length; i++)
  129.         {
  130.             if (snake[i] == 'D')
  131.             {
  132.                 newDirection = 'U';
  133.             }
  134.             else if (snake[i] == 'U')
  135.             {
  136.                 newDirection = 'D';
  137.             }
  138.             else
  139.             {
  140.                 newDirection = snake[i];
  141.             }
  142.  
  143.             newSnake.Append(newDirection);
  144.         }
  145.  
  146.         return newSnake.ToString();
  147.     }
  148.  
  149.     private static string Rotate(string snake)
  150.     {
  151.         var newSnake = new StringBuilder();
  152.         newSnake.Append("S");
  153.  
  154.         char newDirection = ' ';
  155.  
  156.         for (int i = 1; i < snake.Length; i++)
  157.         {
  158.             switch (snake[i])
  159.             {
  160.                 case 'R': newDirection = 'D'; break;
  161.                 case 'D': newDirection = 'L'; break;
  162.                 case 'L': newDirection = 'U'; break;
  163.                 case 'U': newDirection = 'R'; break;
  164.                 default: break;
  165.             }
  166.  
  167.             newSnake.Append(newDirection);
  168.         }
  169.  
  170.         return newSnake.ToString();
  171.     }
  172.     private static string ReverseFlow(string snake)
  173.     {
  174.         var newSnake = new StringBuilder();
  175.         newSnake.Append("S");
  176.  
  177.         char newDirection = ' ';
  178.  
  179.         for (int i = snake.Length - 1; i > 1; i--)
  180.         {
  181.             switch (snake[i])
  182.             {
  183.                 case 'R': newDirection = 'L'; break;
  184.                 case 'D': newDirection = 'U'; break;
  185.                 case 'L': newDirection = 'R'; break;
  186.                 case 'U': newDirection = 'D'; break;
  187.                 default: break;
  188.             }
  189.  
  190.             newSnake.Append(newDirection);
  191.         }
  192.         newSnake.Append("L");
  193.         return newSnake.ToString();
  194.     }
  195. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top