计算在矩阵

Question

的最短距离

字符的矩阵给出如下：

######### 
#P......# 
####..### 
##P....## 
#.......# 
######### 

如何找到P和P之间的最短距离？距离定义为从P移动到P时的总步数。 允许垂直或水平移动一步。 在矩阵中，'＃'代表你无法通过的障碍，'。'代表你可以通过的开放块。

通过简单地将P矩阵从D到P找到距离很容易，但是有没有更有效的方法来解决这个问题？

Answer 1

您可以确定目标的方向，并始终开始寻找该方向的路径。对于像给定的简单矩阵，递归解决方案将立即找到路径，而不是一步之遥。对于更复杂的矩阵，它当然可能被愚弄到死路一条，所以平行的方法可能会更好。

这里的递归方法可能看起来像在C＃：

public static int Distance(string[] matrix, int x, int y, int targetX, int targetY, int fromX, int fromY) { 
    // show where we are 
    Console.WriteLine(x + ", " + y); 
    // check for target 
    if (x == targetX && y == targetY) return 0; 
    // determine valid moves 
    List<Point> move = new List<Point> { 
    new Point(-1, 0), 
    new Point(1, 0), 
    new Point(0, -1), 
    new Point(0, 1), 
    }; 
    move = move.Where(t => x + t.X != fromX || y + t.Y != fromY).ToList(); 
    move = move.Where(t => matrix[y + t.Y][x + t.X] != '#').ToList(); 
    // give up if we are in a dead end 
    if (move.Count == 0) return 1000; 
    // calculate direction towards target 
    double dirX = (targetX - x); 
    double dirY = (targetY - y); 
    double distance = Math.Sqrt(dirX * dirX + dirY * dirY); 
    dirX /= distance; 
    dirY /= distance; 
    // put moves towards the target first 
    move = move.OrderBy(t => Math.Abs(t.X - dirX) + Math.Abs(t.Y - dirY)).ToList(); 
    // look for paths 
    foreach (Point p in move) { 
    int d = Distance(matrix, x + p.X, y + p.Y, targetX, targetY, x, y) + 1; 
    if (d < 1000) return d; 
    } 
    return 1000; 
} 

主营：

string[] matrix = new string[]{ 
    "#########", 
    "#P......#", 
    "####..###", 
    "##P....##", 
    "#.......#", 
    "#########" 
}; 

// find starting and ending points 
List<Point> p = new List<Point>(); 
for (int y=0;y<matrix.Length;y++) { 
    for (int x=0;x<matrix[y].Length;x++) { 
    if (matrix[y][x] == 'P') { 
     p.Add(new Point(x,y)); 
    } 
    } 
} 

// get distance 
int d = Distance(matrix, p[0].X, p[0].Y, p[1].X, p[1].Y, -1, -1); 
Console.WriteLine(d); 

输出：

1, 1 
2, 1 
3, 1 
4, 1 
4, 2 
4, 3 
3, 3 
2, 3 
7