S knight:使用递归的Knight目的地

我一直在研究一个需要骑士的项目(我们在开始时有它的坐标)旅行到目的地(也称为坐标)。我试图使用递归编写,但我的代码似乎没有做任何事情,我找不到问题。这是我的代码:

static bool Kelias(int dabX, int dabY, string[] Lenta, int dX, int dY, int indeksas)
{
    if (dabX == dX && dabY == dY)
        return true;
    if (!Lenta[dabY][dabX].Equals('0'))
    {
        return false;
    }
    if (indeksas > 0)
    {
        StringBuilder naujas = new StringBuilder(Lenta[dabY]);
        naujas[dabX] = (char)indeksas;
        Lenta[dabY] = naujas.ToString();
    }
    // aukstyn desinen
    if (GaliJudeti(dabX + 2, dabY + 1)
            && Kelias(dabX + 2, dabY + 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn desinen
    if (GaliJudeti(dabX + 1, dabY + 2)
            && Kelias(dabX + 1, dabY + 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn kairen
    if (GaliJudeti(dabX - 1, dabY + 2)
            && Kelias(dabX - 1, dabY + 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn kairen
    if (GaliJudeti(dabX - 2, dabY + 1)
            && Kelias(dabX - 2, dabY + 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // zemyn kairen
    if (GaliJudeti(dabX - 2, dabY - 1)
            && Kelias(dabX - 2, dabY - 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // zemyn kairen
    if (GaliJudeti(dabX - 1, dabY - 2)
            && Kelias(dabX - 1, dabY - 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // zemyn desinen
    if (GaliJudeti(dabX + 1, dabY - 2)
            && Kelias(dabX + 1, dabY - 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // zemyn desinen
    if (GaliJudeti(dabX + 2, dabY - 1)
            && Kelias(dabX + 2, dabY - 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    indeksas--;
    return false;
}
static bool GaliJudeti(int x, int y)
{
    if (x >= 0 && y >= 0 && x < 8 && y < 8)
    {
        return true;
    }
    return false;
}

关于变量和我想要做的一点解释:

dabX,dabY-是骑士的当前坐标

Lenta-是我的董事会(这是一个字符串,因为我正在从 txt 文件中读取起始数据)。

dX,dY-是目标目的地

indeksas-是一个跟踪多少移动它需要到达目的地

第二个检查我们正在旅行的坐标是否没有被遮挡(因为我的棋盘是由零组成的,因为它在一个字符串中,我们检查符号是否等于它,如果它不是意味着路径被阻塞)。然后我们进入骑士可能的运动,这是该方法的主要部分。

还有另一个名为 GaliJudeti 的函数,它检查我们是否在董事会的范围内(8x8)。

1

你的代码看起来必须工作。我只是使用你的算法,修改了一下,一切都很好。我使用类来使它看起来更一般,但实际上都是一样的。

static bool MoveFirstSolution(Knight knight, Board board, Point destination, int counter, Trace trace)
{
    board.Set(knight.X, knight.Y, counter);
    if (knight.IsInPoint(destination))
    {       
        //trace is an object to store found path         
        trace.Counter = counter;
        trace.Board = board;                   
        return true;
    }
    counter++;
    Point[] moves = knight.AllPossibleMoves();
    foreach (Point point in moves)
    {
        if (board.Contains(point) && board.IsFree(point))
        {
            knight.MoveTo(point);
            if (MoveFirstSolution(knight, board.GetCopy(), destination, counter, trace))
            {
                return true;
            }
        }
    }
    return false;
}

但是,此功能将找到第一个解决方案并停止。如果您想要最佳解决方案,则即使找到答案也需要继续搜索。

static void Move(Knight knight, Board board, Point destination, int counter, Trace trace)
{
    board.Set(knight.X, knight.Y, counter);
    if (knight.IsInPoint(destination))
    {
        if (!trace.IsShorterThen(counter))
        {
            trace.Counter = counter;
            trace.Board = board;
            Console.WriteLine("Better trace");
            Console.WriteLine("Counter: " + trace.Counter);
            Console.WriteLine(trace.Board);
        }
        return;
    }
    counter++;
    Point[] moves = knight.AllPossibleMoves();
    foreach(Point point in moves)
    {
        if (board.Contains(point) && board.IsFree(point))
        {
            knight.MoveTo(point);
            Move(knight, board.GetCopy(), destination, counter, trace);
        }
    }
}

每次找到更好的跟踪时,跟踪都会被覆盖。但是对于 8 * 8 板,执行需要很长时间。

对于您的代码,我可以建议尝试Console.WriteLine()以确保一切正常。也许,您Lenta没有被覆盖,如您所料,这会导致无限递归。尝试跟踪函数的每个操作,以找到问题的根源。

这是我的主要功能:

static void Main(string[] args)
{
    Knight knight = new Knight(0, 0);
    Board board = new Board(8, 8);
    Point destination = new Point(0, 4);
    Trace bestTrace = new Trace();
    MoveFirstSolution(knight, board, destination, 1, bestTrace);
    Console.WriteLine("Best trace: " + bestTrace.Counter);
    Console.WriteLine(bestTrace.Board);
    Console.ReadLine();
}

和所需的类的其余部分,所以你可以尝试它作为工作的例子。

class Trace
{
    public Trace()
    {
        this.Board = null;
        this.Counter = -1;
    }
    public Trace(Board board, int counter)
    {
        this.Board = board;
        this.Counter = counter;
    }
    public bool IsShorterThen(int counter)
    {
        return this.Counter > 0 && this.Counter <= counter;
    }
    public Board Board { get; set; }
    public int Counter { get; set; }
}
class Board
{
    private int[][] _board;
    public Board(int N, int M)
    {
        this._board = new int[N][];
        for (int i = 0; i < N; i++)
        {
            this._board[i] = new int[M];
            for (int j = 0; j < M; j++)
            {
                this._board[i][j] = 0;
            }
        }
    }
    public int N
    {
        get
        {
            return this._board.Length;
        }
    }
    public int M
    {
        get
        {
            return this._board.Length > 0 ? this._board[0].Length : 0;
        }
    }
    public Board GetEmptyCopy()
    {
        return new Board(this.N, this.M);
    }
    public Board GetCopy()
    {
        Board b = new Board(this.N, this.M);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                b.Set(i, j, this.Get(i, j));
            }
        }
        return b;
    }
    public bool Contains(int i, int j)
    {
        return (i >= 0) && (i < this.N) && (j >= 0) && (j < this.M);
    }
    public bool Contains(Point point)
    {
        return this.Contains(point.X, point.Y);
    }
    public bool IsFree(int i, int j)
    {
        return this._board[i][j] == 0;
    }
    public bool IsFree(Point point)
    {
        return this.IsFree(point.X, point.Y);
    }
    public void Set(int i, int j, int val)
    {
        this._board[i][j] = val;
    }
    public int Get(int i, int j)
    {
        return this._board[i][j];
    }
    public override string ToString()
    {
        string str = "";
        for (int i = 0; i < this.N; i++)
        {
            for (int j = 0; j < this.M; j++)
            {
                str += String.Format("{0, 3}", this._board[i][j]);
            }
            str += "\r\n";
        }
        return str;
    }
}
class Knight
{        
    public Knight(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public int X { get; private set; }
    public int Y { get; private set; }
    public Point[] AllPossibleMoves()
    {
        Point[] moves = new Point[8];
        moves[0] = new Point(this.X + 1, this.Y + 2);
        moves[1] = new Point(this.X + 1, this.Y - 2);
        moves[2] = new Point(this.X + 2, this.Y + 1);
        moves[3] = new Point(this.X + 2, this.Y - 1);
        moves[4] = new Point(this.X - 1, this.Y + 2);
        moves[5] = new Point(this.X - 1, this.Y - 2);
        moves[6] = new Point(this.X - 2, this.Y + 1);
        moves[7] = new Point(this.X - 2, this.Y - 1);
        return moves;
    }
    public bool IsInPoint(int x, int y)
    {
        return this.X == x && this.Y == y;
    }
    public bool IsInPoint(Point point)
    {
        return this.IsInPoint(point.X, point.Y);
    }
    public void MoveTo(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public void MoveTo(Point point)
    {
        this.MoveTo(point.X, point.Y);
    }
}
class Point
{
    public Point(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public int X { get; private set; }
    public int Y { get; private set; }
}

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(568)
Vif检验:多元多元回归的 VIF检验(vif test)
上一篇
Ios手机投屏电脑:完美的闪屏大小的智能手机 平板电脑在Android
下一篇

相关推荐

  • swift 源码字符串、数字、布尔值及其他类型

    Swift 是一种新的编程语言,由 Apple 开发,旨在替代 Objective-C。它支持多种编程范式,包括面向对象、函数式编程和泛型编程。它使用 LLVM 编译器,支持 iOS、macOS、watchOS 和 tvOS 等平台。…

    2023-02-16 08:30:18
    0 71 11
  • python抓取app数据一览无余

    Python抓取APP数据的步骤如下:安装必要的库:使用Python抓取APP数据,需要安装和库,它们可以帮助你获取网页内容并进行解析。…

    2023-04-04 15:44:58
    0 35 66
  • html生日快乐源代码:Happy Birthday!

    2023-10-01 14:19:26
    0 59 28
  • iosbt手游让你的游戏体验更加精彩!

    iOSBT手游是一款基于iOS平台开发的多人在线游戏,玩家可以通过手机或平板电脑上的特定应用程序与其他玩家进行对战。该游戏的特点是简单易学,且拥有多种游戏模式,如团队对战、竞技场对战等。…

    2023-07-20 06:42:32
    0 78 70
  • ios黑色主题:栏```htmlTitle```

    iOS 黑色主题是指将 iOS 应用中的 UI 元素(如导航栏、工具栏、表单等)的颜色设置为黑色,以实现黑色主题的效果。要实现 iOS 黑色主题,需要在应用的 Info.plist 文件中增加一个键值对,其键名为 “”,键值为 “Dark”,代码如下:…

    2023-03-14 13:37:57
    0 41 47
  • ios微信双开tf邀请码:免费领取iOS微信双开TF邀请码,立即加入双开TF体验

    iOS微信双开TF邀请码是一种特殊的代码,用于在iOS设备上安装双开微信应用。这个邀请码可以通过官方微信应用商店或者第三方应用商店获取,也可以从某些网站上获取。…

    2023-04-24 15:16:35
    0 14 90
  • ios 16 beta描述文件更多功能,更多体验

    iOS Beta描述文件是一种特殊的文件格式,用于安装和配置iOS设备上的应用程序。它是一个XML文件,其中包含了一些关于应用程序的信息,包括应用程序的版本号,安装位置,权限,设备要求等等。iOS Beta描述文件的代码如下:…

    2023-08-27 13:25:39
    0 55 64
  • python生成手机app:做出你自己的App,用Python编程实现!

    Python可以用来生成手机应用程序,通过一些框架和工具,可以让你使用Python语言创建出功能强大的手机应用程序。Kivy…

    2023-02-04 10:20:24
    0 78 48

发表评论

登录 后才能评论

评论列表(68条)