最近弄一个消防逃生系统，需要实现 如下图功能，人处于道路上任意一个地址，都指示出通往最近出口的方向。那个算法大师，能告诉我我这个算法能优化吗？同时现在这个算法比较正式的名字叫啥算法？
算法思路:
算法实现如下:
一、定点格子对象
/// <summary> /// 点的对象 /// </summary> public class Cell {public int X { get; private set; }public int Y { get; private set; }/// <summary>/// 格子类型/// </summary>public TileType TileType { get; set; }/// <summary>/// 箭头方向/// </summary>public Direction Direction { get; set; }/// <summary>/// 离最近终点步数/// </summary>public int ToExitStepNumber { get; set; }/// <summary>/// 最近终点/// </summary>public Cell ExitCell { get; set; }/// <summary>/// 上级格子/// </summary>public Cell ParentCell { get; set; }public Cell(int x, int y){X = x;Y = y;}public static bool operator ==(Cell a, Cell b){if (ReferenceEquals(a, b)){return true;}if (((object)a == null) || ((object)b == null)){return false;}return a.X == b.X && a.Y == b.Y;}public static bool operator !=(Cell a, Cell b) => !(a == b);public override bool Equals(object obj) => (this == (Cell)obj);public override int GetHashCode() => X.GetHashCode() ^ Y.GetHashCode(); }public enum TileType {/// <summary>/// 无状态/// </summary>Non = 0,/// <summary>/// 墙/// </summary> Wall,/// <summary>/// 路/// </summary> Road,/// <summary>/// 出口/// </summary> Exit,/// <summary>/// 障碍物/// </summary> Obstacle,/// <summary>/// 临时/// </summary> Temp }/// <summary> /// 行进方向 /// </summary> public enum Direction {/// <summary>/// 无路/// </summary> Non,/// <summary>/// 左/// </summary> Left,/// <summary>/// 上/// </summary> Top,/// <summary>/// 右/// </summary> Right,/// <summary>/// 下/// </summary> Botton }
二、最后实现算法
public class EscapeUtils {/// <summary>/// 逃生工具/// </summary>/// <param name="matrix">当前迷宫的数据化矩阵</param>public EscapeUtils(Cell[][] matrix){this.Matrix = matrix;this.RowCount = matrix[0].Length;this.ColCount = matrix.Length;}/// <summary>/// 找路/// </summary>public void FindRoad(){var exits = new List<Cell>(); // 存放出口的集合foreach (var rows in Matrix) // 遍历所有点，并初始化路径。和找出出口的点 {foreach (var cell in rows){cell.Direction = Direction.Non;cell.ToExitStepNumber = 0;cell.ExitCell = null;if (cell.TileType == TileType.Exit){exits.Add(cell);}}}foreach (var exit in exits) //遍历所有出口 {List<Cell> list = new List<Cell>(); // 声明一个集合存放已找到的点int num = 0;list.Add(exit); // 将当前出口放入集合中do{var nowCell = list[num];var cs = GetNeighbors(nowCell, exit); // 找到当前点能去的所有地址if (cs != null && cs.Count() > 0){list.AddRange(cs); // 将找到的新的地址放入已找到的集合中 }num++;}while (num <= (list.Count - 1)); // 直到找不到新的可去的地址 }}public int ColCount { get; set; }public int RowCount { get; set; }/// <summary>/// 数据矩阵/// </summary>public Cell[][] Matrix { get; set; }private static readonly float[,] neighbors = new float[,]{{ 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }};/// <summary>/// 寻找当前点周围的点到指定终点/// </summary>/// <param name="nowCell">当前节点</param>/// <param name="exit">指定终点</param>/// <returns></returns>public IEnumerable<Cell> GetNeighbors(Cell nowCell, Cell exit){var result = new List<Cell>();for (var i = 0; i < neighbors.GetLongLength(0); i++){var x = nowCell.X + neighbors[i, 0];var y = nowCell.Y + neighbors[i, 1];if (x >= 0 && y >= 0 && x < ColCount && y < RowCount){// 找到上下左右的一个点var nextCell = Matrix[(int)x][(int)y];// 判断该点是否需要更新，不需更新代表不通行 必须是路，且该点没有关联出口或者新的出口距离更短if (nextCell.TileType == TileType.Road && (nextCell.ExitCell == null || nextCell.ToExitStepNumber > nowCell.ToExitStepNumber + 1)){nextCell.ExitCell = exit;nextCell.ToExitStepNumber = nowCell.ToExitStepNumber + 1;nextCell.ParentCell = nowCell;// 比较相邻两个点,求出方向if (nextCell.X == nowCell.X){if (nextCell.Y > nowCell.Y){nextCell.Direction = Direction.Top;}else{nextCell.Direction = Direction.Botton;}}else if (nextCell.Y == nowCell.Y){if (nextCell.X < nowCell.X){nextCell.Direction = Direction.Right;}else{nextCell.Direction = Direction.Left;}}result.Add(nextCell);}}}return result;} }
总结：该算法的消耗，第一个终点会便利所有的路，第二个则会是1/2的点，第三个则是 1/3的点 ····。
最后遍历的总数为 设 路的格子数为 x，出口的格子数为 y ，总遍历数为 z。 那么
z = （1+1/2+1/3+1/4+…+1/y）x 。
可以得到全部路的前进方向。
