fork download 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public struct Tile
  6. {
  7.     public Tile(int x, int y) { X = x; Y = y; }
  8.     public readonly int X;
  9.     public readonly int Y;
  10.     public IEnumerable<Tile> GetNeighbours(int gridSize)
  11.     {
  12.         if (X > 0)
  13.             yield return new Tile(X - 1, Y);
  14.         if (X < gridSize - 1)
  15.             yield return new Tile(X + 1, Y);
  16.         if (Y > 0)
  17.             yield return new Tile(X, Y - 1);
  18.         if (Y < gridSize - 1)
  19.             yield return new Tile(X, Y + 1);
  20.     }
  21.     public override string ToString()
  22.     {
  23.         return string.Format("({0},{1})", X, Y);
  24.     }
  25. }
  26.  
  27. public class Path
  28. {
  29.     public Path(Tile[] tiles) { Tiles = tiles; }
  30.     public Tile[] Tiles { get; private set; }
  31.     public override string ToString()
  32.     {
  33.         return string.Join("", Tiles.Select(tile => tile.ToString()).ToArray());
  34.     }
  35. }
  36.  
  37. public class PathFinder
  38. {
  39.     public IEnumerable<Path> FindPaths(int n, int gridSize)
  40.     {
  41.         if (n == 1)
  42.         {
  43.             for (int x = 0; x < gridSize; ++x)
  44.                 for (int y = 0; y < gridSize; ++y)
  45.                     yield return new Path(new Tile[] { new Tile(x, y) });
  46.         }
  47.         else
  48.         {
  49.             Dictionary<string, object> pathsSeen = new Dictionary<string, object>();
  50.             foreach (Path shortPath in FindPaths(n - 1, gridSize))
  51.             {
  52.                 foreach (Tile tile in shortPath.Tiles)
  53.                 {
  54.                     foreach (Tile neighbour in tile.GetNeighbours(gridSize))
  55.                     {
  56.                         // Ignore tiles that are already included in the path.
  57.                         if (shortPath.Tiles.Contains(neighbour))
  58.                             continue;
  59.  
  60.                         Path newPath = new Path(shortPath.Tiles
  61.                             .Concat(new Tile[] { neighbour })
  62.                             .OrderBy(t => t.X)
  63.                             .ThenBy(t => t.Y)
  64.                             .ToArray());
  65.  
  66.                         string pathKey = newPath.ToString();
  67.                         if (!pathsSeen.ContainsKey(pathKey))
  68.                         {
  69.                             pathsSeen[pathKey] = null;
  70.                             yield return newPath;
  71.                         }
  72.                     }
  73.                 }
  74.             }
  75.         }
  76.     }
  77.  
  78.     static void Main()
  79.     {
  80.         PathFinder pathFinder = new PathFinder();
  81.         for (int n = 1; n <= 9; ++n)
  82.         {
  83.             List<Path> paths = pathFinder.FindPaths(n, n).ToList();
  84.             Console.WriteLine("n = {0}, number of paths found = {1}", n, paths.Count);
  85.             //foreach (Path path in paths)
  86.             //    Console.WriteLine(path.ToString());
  87.         }
  88.     }
  89. }
  90.  
Runtime error #stdin #stdout 0.29s 213760KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HlZib
language:
JavaScript (rhino 1.7.9)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!