第三届华为编程大赛其中一题.docVIP

?? 问题描述 给定N*N字母矩阵，从任意点出发，上，下，左，右移动，在规定方向连续匹配给定的单词序列。即称为命中，否则不命中，字符矩阵中的字母仅能使用一次，不能在同一单元格停留两次。字符矩阵最大50*50，都为大写字母。输入1为字母矩阵，输入2为字母序列，输出是否匹配。 ?? 要求实现函数 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’ ?? 示例 输入：ABCFEDGHI, 3, ABCDEFGHI 返回：1 输入：ABCFEDGAI, 3, ABCDEA 返回：1 输入： ABABABABABABABABABABABABA, 5, ABABABBA 返回： 0 输入： AAAA, 2, AAAA 返回：1 // FindStat.cpp : 定义控制台应用程序的入口点。 // #include stdafx.h #include stdio.h #include string #define Max 50 int getLength(const char *ch) { int i = 0 ; // char newch[Max*Max]; while(ch[i] != NULL) { i++; } return i; } int findPath(const char *Map , unsigned int iArrN , const char *PathStr , int pos) { char map[Max*Max]; char path[Max*Max]; memcpy(map , Map, getLength(Map)); memcpy(path , PathStr+1 , getLength(PathStr)); *(map + getLength(Map)) = NULL; *(path + getLength(PathStr)) = NULL; if(*path == NULL) return 1; if(pos - 1 0 map[pos - 1] == *(path)) { map[pos - 1] = #; if(findPath(map , 3 , path , pos - 1)) return 1; } if(pos - iArrN 0 map[pos - iArrN] == *(path)) { map[pos - iArrN] = #; if(findPath(map , 3 , path , pos - iArrN)) return 1; } if(pos + iArrN iArrN*iArrN - 1 map[pos + iArrN] == *(path)) { map[pos + iArrN ] = #; if(findPath(map , 3 , path , pos + iArrN)) return 1; } if(pos + 1 iArrN*iArrN - 1 map[pos + 1] == *(path)) { map[pos + 1] = #; if(findPath(map , 3 , path , pos + 1)) return 1; } return 0; } int FindStat(const char *Map , unsigned int iArrN , const char *PathStr) { char map[Max*Max]; char path[Max*Max]; int i; memcpy(map , Map, getLength(Map)); memcpy(path , PathStr , getLength(PathStr)); *(map + getLength(Map)) = NULL; *(path + getLength(PathStr)) = NULL; for(i = 0 ; i getLength(Map) ;