lse;
? ? ? ? ? ? }
? ? ? ? }
? ? }
?
? ? return true;
}
?
// Find next Empty Cell
bool FindEmptyCell(const Grid& grid, int& x, int& y)
{
? ? for (int i = 0; i < GRID_SIZE; ++i)
? ? {
? ? ? ? for (int j = 0; j < GRID_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? if (grid[i][j] == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? x = i;
? ? ? ? ? ? ? ? y = j;
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return false;
}
?
void PrintSolution(const Grid& grid)
{
? ? for (int i = 0; i < GRID_SIZE; ++i)
? ? {
? ? ? ? for (int j = 0; j < GRID_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? cout << grid[i][j] << " ";
? ? ? ? }
? ? ? ? cout << "\n";
? ? }
? ? cout << endl;
}
复制代码
【经典回溯问题3】迷宫搜索问题
该问题在实现给定一些黑白方块构成的迷宫，其中黑块表示该方块不能通过，白块表示该方块可以通过，并且给定迷宫的入口和期待的出口，要求找到一条连接入口和出口的路径。有了前面的题目的铺垫，套路其实都是一样的。在当前位置，对于周围的所有方块，判断可行性，对于每一个可行的方块，就是我们当前所有可能的choices；尝试一个choice，递归的判断是否能够导致一个solution，如果可以，return true；否则，尝试另一个choice。如果所有的choice都不能导致一个成功解，return false。剩下的就是递归终止的条件，当前所在位置如果等于目标位置，递归结束，return true。
C++代码如下：
?
复制代码
#include
#include
#include
using namespace std;
?
const int BOARD_SIZE = 4;
enum GridState {Gray, White, Green};
?
const int DIRECTION_NUM = 2;
const int dx[DIRECTION_NUM] = {0, 1};
const int dy[DIRECTION_NUM] = {1, 0};
typedef vector > Grid;
?
?
bool IsSafe(Grid& grid, int x, int y);
bool SolveRatMaze(Grid& grid, int curx, int cury);
void PrintSolution(const Grid& grid);
?
?
int main()
{
? ? vector > grid(BOARD_SIZE, vector(BOARD_SIZE, White));
? ? for (int j = 1; j < BOARD_SIZE; ++j) grid[0][j] = Gray;
? ? grid[1][2] = Gray;
? ? grid[2][0] = Gray; grid[2][2] = Gray; grid[2][3] = Gray;
?
? ? // Place the init position
? ? grid[0][0] = Green;
? ? bool ok = SolveRatMaze(grid, 0, 0);
? ? if (ok)
? ? {
? ? ? ? cout << "Found Solution" << endl;
? ? ? ? PrintSolution(grid);
? ? }
? ? else
? ? {
? ? ? ? cout << "Solution does not exist" << endl;
? ? }
?
? ? return 0;
}
?
?
bool SolveRatMaze(Grid& grid, int curx, int cury)
{
? ? // base case
? ? if (curx == BOARD_SIZE - 1 && cury == BOARD_SIZE - 1) return true;
?
? ? // for every choice
? ? for (int i = 0; i < ? ?DIRECTION_NUM; ++i)
? ? {
? ? ? ? int nextx = curx + dx[i];
? ? ? ? int nexty = cury + dy[i];
? ? ? ? if (IsSafe(grid, nextx, nexty))
? ? ? ? {
? ? ? ? ? ? // try a choice
? ? ? ? ? ? grid[nextx][nexty] = Green;
? ? ? ? ? ? // check whether lead to a solution
? ? ? ? ? ? bool success = SolveRatMaze(grid, nextx, nexty);
? ? ? ? ? ? // if yes, return true
? ? ? ? ? ? if (success) return true;
? ? ? ? ? ? // no, try an alternative choice, backtracking
? ? ? ? ? ? else grid[nextx][nexty] = White;
? ? ? ? }
? ? }
?
? ? // try every choice, still cannot find a solution
? ? return false;
}
?
bool IsSafe(Grid& grid, int x, int y)
{
? ? return grid[x][y] == White;
}
?
void PrintSolution(const Grid& grid)
{
? ? for (int i = 0; i < BOARD_SIZE; ++i)
? ? {
? ? ? ? for (int j = 0; j < BOARD_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? cout << grid[i][j] << " ";
? ? ? ? }
? ? ? ? cout << "\n";
? ? }
? ? cout << endl;
}
复制代码
本文小结
? ? 递归回溯算法想明白了其实很简单，因为大部分工作递归过程已经帮我们做了。再重复一下，递归回溯算法的基本模式：识别出当前格局，识别出当前格局所有可能的choice，尝试一个choice，递归的检查是否导致了一个solution，如果是，直接return true；否则尝试另一个choice。如果尝试了所有的choice，都不能导致一个解，return false从而触发回溯过程。剩下的就是在函数的一开始定义递归终止条件，这个需要具体问题具体分析，一般情况下是，当前格局等于目标格局，递归终止，return false。
?
? ? 在理解了递归回溯算法的思想后，记住经典的permutation问题和子集问题，剩下就是多加练习和思考，基本没有太难的问题。在geekforgeeks网站有一个回溯算法集合Backtracking，题目很经典过一遍基本就没什么问题了