2014雅虎笔试题之矩阵中查找字符串

题目是这样：有一个二维矩阵，里面存的是字符。如：

 A   B   C   D   E

 Y   A    Y   C   D

O   H   B   E    X

O   O   O   B   D

P   O   N   M   G       里面可以查找到YAHOO，要求写函数实现。

bool IsExist(char** mutrix,int** isVisited,int N,int M,int row,int col,char* word)
{
	if (word==NULL||row>=N||row<0||col>=M||col<0) return false;
	if (*word=='\0') return true;
	if (mutrix[row][col]==*word&&isVisited[row][col]==0)
	{
		isVisited[row][col]=1;
		if (IsExist(mutrix,isVisited,N,M,row-1,col,word+1)||IsExist(mutrix,isVisited,N,M,row+1,col,word+1)||IsExist(mutrix,isVisited,N,M,row,col-1,word+1)||IsExist(mutrix,isVisited,N,M,row,col+1,word+1))
		{
			isVisited[row][col]=0;
			cout<<'('<<row<<','<<col<<')'<<' ';
			return true;
		}
		isVisited[row][col]=0;
		return false;
	}
	return false;
}

bool isWordInMutrix(char** mutrix,int N,int M,char* word)
{
	if(mutrix==NULL||N<=0||M<=0) return false;
	if(word==NULL) return true;
	int** isVisited=new int*[N];
	int row,col;
	for (row=0;row<N;++row) isVisited[row]=new int[M];
	for (row=0;row<N;++row)
		for(col=0;col<M;++col)
			isVisited[row][col]=0;
	for (row=0;row<N;++row)
		for(col=0;col<M;++col)
			if (IsExist(mutrix,isVisited,N,M,row,col,word))
			{
				return true;
			}
	return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
	char k[5][5]={{'A','B','C','D','E'},{'Y','A','Y','D','C'},{'O','H','B','E','X'},{'O','O','O','B','D'},{'P','O','N','M','G'}};
	char** mutrix=new char*[5];
	for (int i=0;i<5;i++)
	{
		mutrix[i]=new char[5];
	}
	for(int i=0;i<5;i++)
	{
		for (int j=0;j<5;j++)
		{
			mutrix[i][j]=k[i][j];
		}
	}

	cout<<endl<<isWordInMutrix(mutrix,5,5,"YAHOO")<<endl;

	return 0;
}