学步园

  不知道这是哪一届的最后一题，捣腾一下，见笑。。。

3、路径查找(50分)

l  问题描述

给定N*N字母矩阵，从任意点出发，上，下，左，右移动，在规定方向连续匹配给定的单词序列。即称为命中，否则不命中，字符矩阵中的字母仅能使用一次，不能在同一单元格停留两次。字符矩阵最大50*50，都为大写字母。输入1为字母矩阵，输入2为字母序列，输出是否匹配。

l  要求实现函数

int FindStat(const char *Map, unsigned int iArrN, const char *PathStr)

【输入】Map：        给定的字母矩阵

        iArrN：         字母矩阵的行数

PathStr：         给定的字母序列

【输出】无

【返回】是否能找到命中的单词序列，命中返回1，否则返回0

注：输入矩阵是以一维形式保存的二维数组，

比如输入为{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’,’G’, ‘H’, ‘I’}，

实际上表示如下3*3的矩阵

‘A’,’B’,’C’,

‘D’,’E’,’F’,

‘G’,’H’,’I’

l  示例

输入："ABCFEDGHI", 3, "ABCDEFGHI"

返回：1

输入："ABCFEDGAI", 3, "ABCDEA"

返回：1

输入： "ABABABABABABABABABABABABA", 5, "ABABABBA"

返回： 0

输入： "AAAA", 2, "AAAA"

返回：1

#include <cstdio>
#include <cstring>
#include <cstdlib>
int flag = 0;
#define MAXN 50
int if_vis[MAXN*MAXN];
void dfs(const char *Map, char *start,unsigned int iArrN,char *cur, const char *PathStr,int *if_vis);
int FindStat(const char *Map, unsigned int iArrN, const char *PathStr);


int main()
{
	const char *Map = "ABABABABABABABABABABABABA";
	const char *PathStr = "ABABABBA";
	unsigned int iArrN = 5;
	printf("\n%d\n",FindStat(Map, iArrN, PathStr));
	return 0;
}

void dfs(const char *Map,char *start, unsigned int iArrN, char *cur,const char *PathStr,int *if_vis)
{
    
	int pos = start - (char *)Map;
	if(!if_vis[pos])//若访问过，则返回
		if_vis[pos] = 1;
	else
		return;

	if((cur - PathStr) == (strlen(PathStr)-1))
	{
		flag = 1;
		return;
	}
	
	//上
	int up = pos - iArrN;
	if(up >= 0 && !if_vis[up])
	{
		if(Map[up] == *(++cur))
		{
			dfs(Map,start-iArrN,iArrN,cur,PathStr,if_vis);
			if(flag)
				return;
			else
			{
				if_vis[up] = 0;
				cur--;
			}
		}
		else
		{
			cur--;
		}
	}
	//下
	int down = pos + iArrN;
	if(down <= iArrN*iArrN-1 && !if_vis[down])
	{
		if(Map[down] == *(++cur))
		{
			dfs(Map,start+iArrN,iArrN,cur,PathStr,if_vis);
			if(flag)
				return;
			else	
			{
				if_vis[down] = 0;
				cur--;
			}
		}
		else
		{
			cur--;
		}
	}
    //左
	if(pos%iArrN > 0)
	{
	int left = pos -1;
	if(left >= 0 && !if_vis[left])
	{
		if(Map[left] == *(++cur))
		{
			dfs(Map,start-1,iArrN,cur,PathStr,if_vis);
			if(flag)
				return;
			else
			{
				if_vis[left] = 0;
				cur--;
			}
		}
		else
		{
			cur--;
		}
	}
	}
	//右
	if(pos%iArrN < iArrN)
	{
	int right = pos +1;
	if(right <= iArrN*iArrN-1 && !if_vis[right])
	{
		if(Map[right] == *(++cur))
		{
			dfs(Map,start+1,iArrN,cur,PathStr,if_vis);
			if(flag)
				return;
			else
			{
				if_vis[right] = 0;
				cur--;
			}
		}
		else
		{
			cur--;
			
		}
	}
	}
	
	
	
	
}

int FindStat(const char *Map, unsigned int iArrN, const char *PathStr)
{
    char *start, *tmp = (char *)Map,*cur = (char *)PathStr;
	while((start= strchr(tmp,PathStr[0])) != NULL)
	{
		if(flag)
			break;
		tmp = start+1;
		memset(if_vis,0,(iArrN*iArrN-1)*sizeof(int));
		dfs(Map,start,iArrN,cur,PathStr,if_vis);
		for(int i=0;i < iArrN*iArrN;i++)
		{
			printf("%d ",if_vis[i]);
			if(!((i+1)%iArrN))
				printf("\n");
		}
		printf("\n");
		
	}
	
	
	return flag;
}

思想，从第一个和要匹配子串的首字母相同的位置开始遍历矩阵。。。。。还是比较容易看懂。。。。