题目

一只老鼠位于迷宫左上角(0,0)，迷宫中的数字9处有块大奶酪。0表示墙，1表示可通过路径。试给出一条可行的吃到奶酪的路径；若没有返回空。

假定迷宫是4连通的，即：老鼠只能上下左右走，不能斜着走。

老鼠吃奶酪(老鼠图片大全)

算法描述

这实际上就是练习深度优先搜索。

PS：个人感觉深度优先搜索就是个有点门道的暴力求解….

解法：假定当前位于(i,j)处，则依次计算(i-1,j),(i+1,j),(i,j-1), (i,j+1)4个相邻位置，如果相邻位置不是墙，则可以通过。然后递归该过程。

代码

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;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/125382.html原文链接：https://javaforall.net