好的，会有极端数量的可能的动作序列，正如评论所暗示的那样。 这是从我的头顶，我是如此裸露....
非递归版本：你需要的位置列表的列表（称为位置列表），这将是你最后的答案，我会将该列表称为路由列表。
为每个起始位置创建一个列表，并将它们全部放入路由列表中。
While the routes list has a position list that's less than the required length
{
Get a position list that's too short.
Remove it from the routes list
Create new position lists that are a copy of the list we just removed + a possible next position from the last position in the list.
Add those lists to the routes list.
}
编辑：递归版本：
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
static int GridSize = 5;
static void Main(string[] args)
{
List<List<Point>> Positions = (from X in Enumerable.Range(0, GridSize)
from Y in Enumerable.Range(0, GridSize)
select new List<Point>() { new Point(X, Y) }).ToList();
var PossibleRoutes = WalkGraph(Positions, 5);
}
static List<List<Point>> WalkGraph(List<List<Point>> RoutesList, int DesiredLength)
{
List<List<Point>> Result = new List<List<Point>>();
foreach (var Route in RoutesList)
{
if (Route.Count < DesiredLength)
{
// Extend the route (produces a list of routes) and recurse
Result.AddRange(WalkGraph(ExtendRoute(Route), DesiredLength));
}
else
{
Result.Add(Route);
}
}
return Result;
}
static List<List<Point>> ExtendRoute(List<Point> Route)
{
List<List<Point>> NextMoveRoutes = new List<List<Point>>();
// Itterate through each possible move
foreach (var NextMove in PossibleMoves(Route.Last()))
{
// Create a copy of the route, and add this possible move to it.
List<Point> NextMoveRoot = new List<Point>(Route);
NextMoveRoot.Add(NextMove);
NextMoveRoutes.Add(NextMoveRoot);
}
return NextMoveRoutes;
}
static List<Point> PossibleMoves(Point P)
{
// TODO Generate a list of possible places to move to
List<Point> Result = new List<Point>();
Result.Add(new Point(P.X + 1, P.Y + 2));
Result.Add(new Point(P.X - 1, P.Y + 2));
Result.Add(new Point(P.X + 1, P.Y - 2));
Result.Add(new Point(P.X - 1, P.Y - 2));
Result.Add(new Point(P.X + 2, P.Y + 1));
Result.Add(new Point(P.X - 2, P.Y + 1));
Result.Add(new Point(P.X + 2, P.Y - 1));
Result.Add(new Point(P.X - 2, P.Y - 1));
Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
PossibleMove.Y < 0 || PossibleMove.Y > GridSize);
return Result;
}
}
}
编辑：下面是一个使用IEnumerable的，以消除最初的计算时间，并大幅降低内存占用一个版本。
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
static int GridSize = 5;
static void Main(string[] args)
{
IEnumerable<IEnumerable<Point>> Positions = from X in Enumerable.Range(0, GridSize)
from Y in Enumerable.Range(0, GridSize)
select new List<Point>() { new Point(X, Y) } as IEnumerable<Point>;
var PossibleRoutes = WalkGraph(Positions, 100);
foreach (var Route in PossibleRoutes)
{
Console.WriteLine(Route.Select(P => P.ToString()).Aggregate((curr, next) => curr + " " + next));
//Thread.Sleep(500); // Uncomment this to slow things down so you can read them!
}
Console.ReadKey();
}
static IEnumerable<IEnumerable<Point>> WalkGraph(IEnumerable<IEnumerable<Point>> RoutesList, int DesiredLength)
{
foreach (var Route in RoutesList)
{
if (Route.Count() < DesiredLength)
{
// Extend the route (produces a list of routes) and recurse
foreach (var ExtendedRoute in WalkGraph(ExtendRoute(Route), DesiredLength))
yield return ExtendedRoute;
}
else
{
//Result.Add(Route);
yield return Route;
}
}
}
static IEnumerable<IEnumerable<Point>> ExtendRoute(IEnumerable<Point> Route)
{
// Itterate through each possible move
foreach (var NextMove in PossibleMoves(Route.Last()))
{
// Create a copy of the route, and add this possible move to it.
List<Point> NextMoveRoute = new List<Point>(Route);
NextMoveRoute.Add(NextMove);
yield return NextMoveRoute;
}
}
static IEnumerable<Point> PossibleMoves(Point P)
{
List<Point> Result = new List<Point>();
Result.Add(new Point(P.X + 1, P.Y + 2));
Result.Add(new Point(P.X - 1, P.Y + 2));
Result.Add(new Point(P.X + 1, P.Y - 2));
Result.Add(new Point(P.X - 1, P.Y - 2));
Result.Add(new Point(P.X + 2, P.Y + 1));
Result.Add(new Point(P.X - 2, P.Y + 1));
Result.Add(new Point(P.X + 2, P.Y - 1));
Result.Add(new Point(P.X - 2, P.Y - 1));
Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
PossibleMove.Y < 0 || PossibleMove.Y > GridSize);
return Result as IEnumerable<Point>;
}
}
}
您可能希望查看LinkedList数据结构。你有没有与你的教授核对，以确认你是否在正确的轨道与偷窥代码碰巧？因为我之前从未做过这样的项目，究竟是什么使移动成为有效的，只是连接到正方形的网格上的正方形是正确的？ – 2011-05-05 11:56:08
您是否被要求列出所有旅行团，或者统计到达每个广场的方式数量，或者究竟是什么？如果你被要求列出所有的旅行团，那么你列出他们的顺序是否有关系？ – 2011-05-05 12:01:33