题目描述

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

题解：回溯法

算法思路：

回溯法首先要找到矩阵的入口是在哪里，因此，第一步是要找到入口
走过的路径不能在走，因此，用一个辅助数组（该数组同矩阵行列相同，元素初始化为0，走过的正确的路径记为1）.
通过一个计数器堆路径的字符串进行计数，当计数器数和字符串字符数相同时，找到路径。
路径不对时，需要回退。回退之和辅助数组的归0，计数器--

本题递归出口条件

下标超出边界
矩阵字符不是字符串的对应字符
矩阵中路径已经被正确走过

代码

#include<iostream>
using namespace std;
#include<vector>
//递归函数
void dfs(vector<vector<char>> matrix, int& count, int row, int col, string str, vector<vector<bool>>& visited) {
	if (row < 0 || row > matrix.size() - 1 || col < 0 || col > matrix[0].size() - 1)
		return; //出口条件：超出边界，返回
	if (matrix[row][col] != str[count])
		return; //出口条件：移动的单元格不是对应的字符，返回
	if (visited[row][col] == 1)
		return; //出口条件：最终当对应位置全部被走过后，返回

	//找到对应的字符后
	visited[row][col] = 1;//把每次成功找到的走过的路径上的字符设置为真
	count++;//每一次找到了之后，count=count+1
	if (count == str.size()) return; //所有字符找到，返回

	//开始向四个方向递归
	dfs(matrix, count, row - 1, col, str, visited);
	dfs(matrix, count, row + 1, col, str, visited);
	dfs(matrix, count, row, col - 1, str, visited);
	dfs(matrix, count, row, col + 1, str, visited);
	//如果不采用循环方式进行四个方向的递归，那么就必须在四个方向递归完毕之后
	//还没有找到对应的字符，说明有重复元素，就需要进行回退，count--；
	//如果全部找到了，返回,count不能再改变，需要作为getIn的判断条件。
	if (count == str.size())
		return;
	else {
		count--;//当四个方向都不是对应字符，说明上一个字符位置不对
		visited[row][col] = 0;//返回时候，count和visited都要更改
	}
}
//找入口位置，即是字符串的第一个元素在矩阵中的位置
bool getIn(vector<vector<char>> matrix,int row, int col, string str) {
	if (matrix[row][col] != str[0]) return false;//没有找到入口，即是第一个字符
	//找到入口，开始递归
	int count = 0;//路径字符数计数
	//定义一个bool型二维数组，同时进行初始化，用来存放已经被访问过的单元格
	vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), 0));
	dfs(matrix, count, row, col, str, visited);

	if (count == str.size())//当找到的个数和字符串相同时，返回true，否在返回false;
		return true;
	return false;
}
bool hasPath(vector<vector<char>> matrix, string word) {
	// write code here
	int rowLen = matrix.size();//行数
	int colLen = matrix[0].size();//列数
	//找第一个字符所在位置,如果第一个位置找到了，但是不对，重新查找
	//即使先找到真正的入口，而题目“机器人的运动范围”之所以不需要找入口，
	//是因为入口提前已经告知了。
	for (int i = 0; i < rowLen; i++)
	{
		for (int j = 0; j < colLen; j++)
		{
			if (getIn(matrix, i, j, word))
				return true;
		}
	}
	return false;
}

int main() {
	vector<vector<char>> matrix;

	//vector<char> v1 = { 'a','b','c','e','h','j','i','g' };
	//vector<char> v2 = { 's','f','c','s','l','o','p','q' };
	//vector<char> v3 = { 'a','d','e','e','m','n','o','e'};
	//vector<char> v4 = { 'a','d','i','d','e','j','f','m' };
	//vector<char> v5 = { 'v','c','e','i','f','g','g','s' };
	//vector<char> v1 = { 'a','b','c','e' };
	//vector<char> v2 = { 's','f','c','s' };
	//vector<char> v3 = { 'a','d','e','e' };
	vector<char> v1 = { 'a','b','c' };
	vector<char> v2 = { 'b','e','d' };
	vector<char> v3 = { 'f','g','g' };
	matrix.push_back(v1);
	matrix.push_back(v2);
	matrix.push_back(v3);
	//matrix.push_back(v4);
	//matrix.push_back(v5);

	string str = "abcdebf"; 
	cout << "是否存在路径abcdebf：" << hasPath(matrix, str) << endl;

	system("pause");
	return 0;
}

JZ12-题解 | #矩阵中的路径#

题目描述