棋Che上的骑士最短路径 [英] Knight's Shortest Path on Chessboard

问题描述

我一直在为即将到来的编程比赛做练习，但偶然发现了一个令我完全困惑的问题。但是，我觉得这似乎是我现在应该学习的概念，而不是用手指指望它永远不会出现。

I've been practicing for an upcoming programming competition and I have stumbled across a question that I am just completely bewildered at. However, I feel as though it's a concept I should learn now rather than cross my fingers that it never comes up.

基本上，它处理象棋上的骑士棋子板。系统将为您提供两个输入：开始位置和结束位置。然后目标是计算并打印骑士可以到达目标位置的最短路径。

Basically, it deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.

我从来没有处理过最短路径的东西，甚至都不知道从哪里开始。我应采用什么逻辑来解决这个问题？

I've never dealt with shortest-path-esque things, and I don't even know where to start. What logic do I employ to go about tackling this?

P.S。如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以（可能）进行的（可能）八次移动所形成的正方形的四个角来补充骑士的正常移动，因为正方形的中心是骑士的位置。

P.S. If it's of any relevance, they want you to supplement the knight's normal moves by also allowing it to move to the four corners of the square formed by the (potentially) eight moves a knight can make, given that the center of the square is the knight's location.

推荐答案

您在这里有一个图形，其中所有可用的动作都已连接（值= 1），而不可用的动作是断开连接（值= 0），则稀疏矩阵将类似于：

You have a graph here, where all available moves are connected (value=1), and unavailable moves are disconnected (value=0), the sparse matrix would be like:

(a1,b3)=1,
(a1,c2)=1,
  .....

最短路径可以使用 http://en.wikipedia.org/wiki/Dijkstra找到图表中的两个点's_algorithm

来自维基百科页面的伪代码：

Pseudo-code from wikipedia-page:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

编辑：

1. ，表示使用
   http://en.wikipedia.org/wiki/A*_algorithm
   可以更快。


2. 最快的方法是
   来预先计算所有距离
   并将其保存到8x8全屏矩阵。
   很好，我将其称为作弊
   ，并且仅因为问题
   小而起作用。但是有时候比赛
   会检查您的程序
   运行的速度。


3. 要点是，如果您正在为编程比赛准备
   ，则必须知道包括Dijkstra算法在内的
   常见算法。
   一个很好的起点是阅读
   算法简介 ISBN 0-262-03384-4。
   或者您可以尝试Wikipedia， http://en.wikipedia.org/wiki/List_of_algorithms

1. as moron, said using the http://en.wikipedia.org/wiki/A*_algorithm can be faster.
2. the fastest way, is to pre-calculate all the distances and save it to a 8x8 full matrix. well, I would call that cheating, and works only because the problem is small. But sometimes competitions will check how fast your program runs.
3. The main point is that if you are preparing for a programming competition, you must know common algorithms including Dijkstra's. A good starting point is reading Introduction to Algorithms ISBN 0-262-03384-4. Or you could try wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms

这篇关于棋Che上的骑士最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！