https://moonstonelin.wordpress.com/2016/05/27/maze/
有个迷宫游戏，从网上找了一个类似的，大家可以玩一下：http://www.bigfishgames.com/online-games/4038/slide-maze/index.html。注意跟一般迷宫游戏不同的是，小人只有到墙或者boundary才停下来，我们无法控制小人走的步数。
写一个function，输入是这个迷宫，小人的起始位置，和他的目的地。要求输出一个move的序列，使小人能从起点到终点。
以链接里那个游戏的level one为例，输出（’Down’,’Right’,’Down’,’Right’,’Down’,’Left’,’Down’,’Left’,’Up’,’Left’)。
public List<List<Direction>> Maze(int[,] matrix, int startRow, int startColumn, int endRow, int endColumn){ Dictionary<Tuple<int, int>, Tuple<int, int>> Lefts = new Dictionary<Tuple<int, int>, Tuple<int, int>>(); Dictionary<Tuple<int, int>, Tuple<int, int>> Rights = new Dictionary<Tuple<int, int>, Tuple<int, int>>(); Dictionary<Tuple<int, int>, Tuple<int, int>> Ups = new Dictionary<Tuple<int, int>, Tuple<int, int>>(); Dictionary<Tuple<int, int>, Tuple<int, int>> Downs = new Dictionary<Tuple<int, int>, Tuple<int, int>>(); int R = matrix.GetLength(0); int C = matrix.GetLength(1); for (int r = 0; r < R; r++) { // <<-- int stopColumn = 0; for (int c = 0; c < C; c++) { if (matrix[r, c] == 0) { if ((c - 1 >= 0) && (matrix[r, c - 1] == 1)) { stopColumn = c; } Lefts.Add(new Tuple<int, int>(r, c), new Tuple<int, int>(r, stopColumn)); } } // -->> stopColumn = C - 1; for (int c = C-1; c >= 0; c--) { if (matrix[r, c] == 0) { if ((c + 1 < C) && (matrix[r, c + 1] == 1)) { stopColumn = c; } if ((r == endRow) && (c == endColumn)) { stopColumn = c; } Rights.Add(new Tuple<int, int>(r, c), new Tuple<int, int>(r, stopColumn)); } } } for (int c = 0; c < C; c++) { // up int stopRow = 0; for (int r = 0; r < R; r++) { if (matrix[r, c] == 0) { if ((r - 1 >= 0) && (matrix[r - 1, c] == 1)) { stopRow = r; } if ((r == endRow) && (c == endColumn)) { stopRow = r; } Ups.Add(new Tuple<int, int>(r, c), new Tuple<int, int>(stopRow, c)); } } // down stopRow = R - 1; for (int r = R - 1; r >= 0; r--) { if (matrix[r, c] == 0) { if ((r + 1 < C) && (matrix[r + 1, c] == 1)) { stopRow = r; } if ((r == endRow) && (c == endColumn)) { stopRow = r; } Downs.Add(new Tuple<int, int>(r, c), new Tuple<int, int>(stopRow, c)); } } } List<List<Direction>> result = new List<List<Direction>>(); Stack<Direction> stack = new Stack<Direction>(); HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>(); Helper(startRow, startColumn, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack); return result;}private void Helper(int startRow, int startColumn, int endRow, int endColumn, HashSet<Tuple<int, int>> visited, Dictionary<Tuple<int, int>, Tuple<int, int>> Lefts, Dictionary<Tuple<int, int>, Tuple<int, int>> Rights, Dictionary<Tuple<int, int>, Tuple<int, int>> Ups, Dictionary<Tuple<int, int>, Tuple<int, int>> Downs, List<List<Direction>> result, Stack<Direction> stack){ Tuple<int, int> t = new Tuple<int, int>(startRow, startColumn); if (visited.Contains(t)) { return; } visited.Add(t); if ((startRow == endRow) && (startColumn == endColumn)) { List<Direction> ds = new List<Direction>(); ds.AddRange(stack); ds.Reverse(); result.Add(ds); return; } Tuple<int, int> key = new Tuple<int, int>(startRow, startColumn); if (Lefts.ContainsKey(key)) { stack.Push(Direction.Left); Helper(Lefts[key].Item1, Lefts[key].Item2, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack); stack.Pop(); } if (Rights.ContainsKey(key)) { stack.Push(Direction.Right); Helper(Rights[key].Item1, Rights[key].Item2, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack); stack.Pop(); } if (Ups.ContainsKey(key)) { stack.Push(Direction.Up); Helper(Ups[key].Item1, Ups[key].Item2, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack); stack.Pop(); } if (Downs.ContainsKey(key)) { stack.Push(Direction.Down); Helper(Downs[key].Item1, Downs[key].Item2, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack); stack.Pop(); }}