void MousePath(const vector<vector<int>>& chess)
{
	// 棋盘都是坐标，于是用int表示
	vector<pair<int, int>> path;
	// 初始化棋盘，所有值都标为False，即每个左边都还未被访问过
	vector<vector<bool>> visit(chess.size(),vector<bool>(chess[0].size(), false));
	// 开始路径搜索
	path.push_back(make_pair(0, 0));	// 从0,0开始
	visit[0][0] = true;	// 0,0被访问过
	Search( chess, 0, 0, path, visit ); // 开始搜索，对于棋盘chess，从0,0开始，记录路径path，访问的节点放置在visit。
}

bool Search(const vector< vector<int>>& chess, int i, int j, vector<pair<int, int>>&path, vector<vector<bool>>&visit)
{
	// 如果为9，那就找到了，打印path，返回ture
	if(chess[i][j] == 9) {
		Print(path);
		return true;
	}
	// 相对于当前的(i,j)点，(i-1, j)，(i+1, j)，(i, j-1)，(i, j+1) 就是(-1, 0)，(1, 0)，(0, -1)，(0, 1)，于是iNext就是这四个点的i值，jNext就是相应的j值。
	int iNext[] = {0, 0, -1, 1};
	int jNext[] = {-1, 1, 0, 0};
	int iCur, jCur;
	// 棋盘大小是m*n的
	int m = (int)chess.size();
	int n = (int)chess[0].size();
	// 4代表4连通。
	for(int k = 0, k < 4; k++) {
		// 当前的(i,j)偏移一位。
		iCur = i+iNext[k];
		jCur = j+jNext[k];
		// 如果越界，则不可行
		if((iCur < 0) || (iCur >= m ) || (jCur < 0) || (jCur >= n ) continue;
		// 要求iCur和jCur从来没到达过且不是墙
		if(!visit[iCur][jCur] && (chess[iCur][jCur] != 0)) {
			// 把iCur和jCur放置在路径中
			path.push_back(make_pair(iCur, jCur));
			// 把iCur和jCur设置为已访问
			visit[iCur][jCur] = true;
			// 继续搜索
			if(Search(chess, iCur, jCur, path, visit)) {
				// 如果求所有路径，则将下句替换成all.push_back(path);
				return true;
			}
			// 从(iCur,jCur)找不到可行路径，把iCur和jCur pop出去，然后回溯一下继续探测。
			path.pop_back();
			visit[iCur][jCur] = false;
		}
	}
	return false;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：老鼠吃奶酪，转载请注明来源！