資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究如何使用 C# 找到馬到達目的所需的最少步數？
馬必須覆蓋棋盤的所有單元格，並且只能在單元格上移動一次。
有兩種方法可以完成馬的移動——第一種方法是馬距離最初開始位置相距一格，因此它可以從開始的位置移動並形成迴圈，這稱為閉合迴圈，第二種方法是它在其他任何位置結束，這稱為開放迴圈。如果馬在棋盤內部且該單元格未被佔用，則該移動有效。我們將使所有未佔據單元格的值等於 -1。
示例
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class KnightWalkProblem{
public class cell{
public int x, y;
public int dis;
public cell(int x, int y, int dis){
this.x = x;
this.y = y;
this.dis = dis;
}
}
static bool isInside(int x, int y, int N){
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
public int minStepToReachTarget(int[] knightPos, int[] targetPos, int N){
int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
Queue<cell> q = new Queue<cell>();
q.Enqueue(new cell(knightPos[0], knightPos[1], 0));
cell t;
int x, y;
bool[,] visit = new bool[N + 1, N + 1];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visit[i, j] = false;
visit[knightPos[0], knightPos[1]] = true;
while (q.Count != 0){
t = q.Peek();
q.Dequeue();
if (t.x == targetPos[0] && t.y == targetPos[1])
return t.dis;
for (int i = 0; i < 8; i++){
x = t.x + dx[i];
y = t.y + dy[i];
if (isInside(x, y, N) && !visit[x, y]){
visit[x, y] = true;
q.Enqueue(new cell(x, y, t.dis + 1));
}
}
}
return int.MaxValue;
}
}
class Program{
static void Main(string[] args){
KnightWalkProblem kn = new KnightWalkProblem();
int N = 30;
int[] knightPos = { 1, 1 };
int[] targetPos = { 30, 30 };
Console.WriteLine(
kn.minStepToReachTarget(
knightPos,
targetPos, N));
}
}
}
輸出
20
更新於：2021-08-27
273 次瀏覽
廣告