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].Item
1
, Lefts[key].Item
2
, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack);
stack.Pop();
}
if (Rights.ContainsKey(key))
{
stack.Push(Direction.Right);
Helper(Rights[key].Item
1
, Rights[key].Item
2
, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack);
stack.Pop();
}
if (Ups.ContainsKey(key))
{
stack.Push(Direction.Up);
Helper(Ups[key].Item
1
, Ups[key].Item
2
, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack);
stack.Pop();
}
if (Downs.ContainsKey(key))
{
stack.Push(Direction.Down);
Helper(Downs[key].Item
1
, Downs[key].Item
2
, endRow, endColumn, visited, Lefts, Rights, Ups, Downs, result, stack);
stack.Pop();
}
}