## Thursday, June 9, 2016

### Slide Maze

https://moonstonelin.wordpress.com/2016/05/27/maze/
有个迷宫游戏，从网上找了一个类似的，大家可以玩一下：http://www.bigfishgames.com/online-games/4038/slide-maze/index.html。注意跟一般迷宫游戏不同的是，小人只有到墙或者boundary才停下来，我们无法控制小人走的步数。
写一个function，输入是这个迷宫，小人的起始位置，和他的目的地。要求输出一个move的序列，使小人能从起点到终点。

`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();`
`    ``}`
`}`