请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中

时间：2022-09-06 15:48:00

// test20.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<vector>

#include<string>

#include<queue>

#include<stack>

#include<cstring>

#include<string.h>

#include<deque>

#include <forward_list>

using namespace std;

class Solution {

public:

	char* flag;

	bool hasPath(char* matrix, int rows, int cols, char* str)

	{

		flag = str;

		if (matrix == NULL || str == NULL) return false;

		char* current = matrix;

		char* tempStr= matrix;

		bool result = false;

		while (tempStr <matrix +rows*cols)

		{

		/*	cout << "*current:" << *current << "  ";

			cout << "*str:" << *str << endl;*/

			if (*tempStr == *str)

			{

				visisted.clear();//不要忘了清楚visisted！！！！！！！！！！！！！！（问题1）

				setVisisted(rows, cols);

				char* current = tempStr;

				cout << "*current:" << *current << "  ";

				cout << "*str:" << *str << endl;

				result = getPath(matrix,rows,cols, str, current);

				cout << endl << endl;;

			}

			if (result == true) break;

			++tempStr;

		}

		return result;

	}

	bool getPath(char* matrix, int rows, int cols, char* str, char* current)

	{

		if (*str == '\0')return true;//注意：此句话放在不同的位置得出的结论是不同的，不能放在下面的位置！！！！！！！！！！！！！（问题3）

		if (current < matrix || current >= matrix + rows*cols) return false;

		if(visisted[current - matrix]==true)return false;

	//	visisted[current - matrix] = true;//当该数符合要求才设置为true!!!!!!!!!!!!!!设置在此处是错误的！！！！！！！！！！（问题2）

		//if (*str == '\0')return true;//注意，!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

		cout << "*str:" << *str << "   ";

		cout << "*current:" << *current << endl;

		cout << "str的下标:" << str - flag<<"  " ;

		cout << "current的下标:" << current - matrix << endl;

		if (*str != *current) return false;

		//if (*str == *current)//两者相等

		visisted[current - matrix] = true;//当该数符合要求才设置为true!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	return getPath(matrix, rows, cols, str + 1, current - 1) ||

			getPath(matrix, rows, cols, str + 1, current + 1) ||

			getPath(matrix, rows, cols, str + 1, current - cols) ||

			getPath(matrix, rows, cols, str + 1, current + cols);

	}

	vector<bool> visisted;//访问标志数组，如果已经被访问，则设置为true，以后不可被访问

	void setVisisted(int rows,int cols)

	{

		int i = 0;

		while (i<rows*cols)

		{

			visisted.push_back(false);

			++i;

		}

	}

};

int main()

{

	Solution so;

	//cout << 1 / 10 << endl;

	//char* matrix = "abcesfcsadee";

	//char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";

	//char* str = "SLHECCEIDEJFGGFIE";

	char* matrix = "AAAAAAAAAAAA";

	char* str = "AAAAAAAAAAAA";

	char* str1 = "bcced";

	char* str2 = "abcb";

	char* str3 = "abc";

	int rows = 3;

	int cols = 4;

	//cout<<"bcced匹配结果是："<<so.hasPath(matrix, rows, cols, str1)<<endl;

	//cout << "abcb匹配结果是：" << so.hasPath(matrix, rows, cols, str2) << endl;

	//cout << "abc匹配结果是：" << so.hasPath(matrix, rows, cols, str3) << endl;

	cout << "SLHECCEIDEJFGGFIE匹配结果是：" << so.hasPath(matrix, 3, 4, str) << endl;

	return 0;

}

相关文章