好的，會有極端數量的可能的動作序列，正如評論所暗示的那樣。 這是從我的頭頂，我是如此裸露....
非遞歸版本：你需要的位置列表的列表（稱爲位置列表），這將是你最後的答案，我會將該列表稱爲路由列表。
爲每個起始位置創建一個列表，並將它們全部放入路由列表中。
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