到年底，同时将通过所有需要的点 [英] Reach end while going through all required points

问题描述

鉴于宽度W和高度H的含有5型符号的格

Given a grid of width W and height H containing 5 type of symbols :

'S' means starting position
'E' means ending position
'C' means checkpoints
'.' means open position and player can pass through it
'#' means closed block that player cant pass through.

播放器的目的是从开始的最短距离到达终点，而是他需要通过所有检查点在网格中。

The aim of the player is to reach end from start in minimum distance but he need to pass all the checkpoints in the grid .

我们需要找到这个最小距离。

We need to find this minimum distance.

一些允许球员动作有：

1. 玩家只能在水平或垂直（上，下，左，右）的方向一步移动。
2. 在对角线移动是不允许的。
3. 距离被定义为运动到不同的块数。
4. 玩家可以通过打开块，检查站，并启动不止一次如果有必要更多的终点。
5. 如果其不能在目标到达，从开始那么我们需要告诉它不可能。

例如：

让 W = 5 和 H = 5

# # # # #
# . C C #
# S # # #
# . . E #
# # # # #

那么这里的答案是9的路径是：

Then here answer is 9 as path is :

（1,2）=>（1,1）=>（2,1）=>（3,1）=>（2,1）=>（1,1，）=>（1,2- ）=>（1,3）=>（2,3）=>（3,3）

(1,2)=>(1,1)=>(2,1)=>(3,1)=>(2,1)=>(1,1,)=>(1,2)=>(1,3)=>(2,3)=>(3,3)

现在是W 和 ^ h 可高达100和检查站的最大数量可在最高18

Now W and H can go up to 100 and maximum number of checkpoints can be at max 18

其中的基本方法可以用在here.But所有对的最短路径作为他们可以如此的复杂度为O（N ^ 3）使用10000节点像弗洛伊德 - 沃肖尔或者Dijkstra的算法的不会达到目的。

One of a basic approach can be to use all pair shortest path in here.But As their can be 10000 nodes so complexity of O(N^3) by using alogrithms like Floyd-Warshall Or Dijkstra's will not serve the purpose.

那么，他们对这个问题的一个更好的办法？

So is their an better approach for this question?

推荐答案

使用寻路算法如 A * 中找到两个点之间的路径，那么你必须分解你的问题为以下几点： -

Use pathfinding algorithm like A* to find paths between two points then you have to decompose your problem into following :-

cost(S,E) = cost(S,C1)+cost(C2,C3)..cost(C3,C4)..cost(Ck,E)

有 K！ K 检查点的顺序，以便你的算法将 O（ ķ！* N ^ 2）键，不可能有更好的算法，因为这问题简化为 TSP 。

There are k! sequence of k checkpoints so your algorithm will be O(k!*N^2) and there cannot be better algorithm as this problem is reduced to TSP.

这篇关于到年底，同时将通过所有需要的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！