Introduction
[ Rat in a maze problem ](http://algorithms.tutorialhorizon.com/backtracking-
rat-in-a-maze-puzzle/ “Rat in a maze problem”) ，是用 回溯法
求解迷宫问题的经典例题。回溯法是一种优选的搜索法，根据择优的条件向前或向后搜索，最终获得目标。当向前搜索到某一步，根据目标函数得到的结果不是最优时，进行回溯，重新选择探索方向。由此得到最优解。
回溯法解决问题的基本步骤一般为：
- 根据给定问题，定义目标函数，并保证该问题至少有一个解
- 确定搜索的空间结构，确保回溯法可以遍历整个解空间
- 通过深度优先算法的形式，搜素整个解空间，并通过适当剪纸来减少冗余的搜索
回溯法的一个应用场景便是解决迷宫问题。
Requirement
In this problem you will solve the “Rat in a maze problem”, using Stacks and
Queues (Lectures 12-14).
The main points we shall be covering are:
- Using Stacks and Queues in an application
- Re-enforcement of the usage and advantages of makefiles / make utility in UNIX/Linux
- Use of abstract data types in C++, and separate compilation
- Use of header files and libraries for Stacks and Queues
Analysis
本题需要采用 Stack 和 Queue
来解决迷宫问题。
栈用于存放回溯算法中的搜索路径，由于栈的后进先出特性，可以很容易的实现回溯。
队列用于存放已经搜索过的最优路径，由于队列的先进先出特性，可以很容易的进行目标函数的计算。
目标函数：从(0, 0)走到(N, N)的 Taxicab geometry
，也就是
曼哈顿距离 。
Tips
题目搜给的迷宫为
—|—
我们需要利用回溯法，从左上角走到右下角
下面给出程序的回溯搜索算法部分的代码
static bool SearchEngine::DoMove(int movePosition) {
…
switch (movePosition) {
case MOVE_LEFT:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_RIGHT);
break;
case MOVE_UP:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_DOWN);
break;
case MOVE_RIGHT:
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_LEFT);
break;
case MOVE_DOWN:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_UP);
break;
default:
break;
}
…
return true;
}
—|—
