1.题目分析
题目如下所示：
简单来说。输入为矩阵维度，所需要搜索的单词，输出判定。具体涉及到，二维可变维度矩阵的声明和定义，基于“树”的搜索算法的设计。本文使用了vector。
2.程序代码
#include "stdafx.h"#include"iostream"#include"vector"#include"string"using namespace std;//四个搜索方向const int r[4]={-1,0,1,0};const int c[4]={0,1,0,-1};//搜索函数bool find(string word,int index,char** maze,bool** ableVisitFlag,bool** alreadyUseFlag,int i,int j){ if(index==word.size()) return true; for(int k=0;k<4;k++) { if(ableVisitFlag[i+r[k]][j+c[k]]&&!alreadyUseFlag[i+r[k]][j+c[k]]&&maze[i+r[k]][j+c[k]]==word[index]) { alreadyUseFlag[i+r[k]][j+c[k]]=true; if(find(word,index+1,maze,ableVisitFlag,alreadyUseFlag,i+r[k],j+c[k]))//迭代 return true; alreadyUseFlag[i+r[k]][j+c[k]]=false;//当前节点的所有下一步遍历均失败，故修改至“false” } } return false;}int _tmain(int argc, _TCHAR* argv[]){ //变量定义 int row,col; string word;//匹配单词 bool flag=false; cin>>row>>col>>word; char**maze=new char*[row+2];//迷宫矩阵 bool**ableVisitFlag=new bool*[row+2];//当前模式中，该字母能被访问(true)，配合四个搜索方向使用 bool**alreadyUseFlag=new bool*[row+2];//当前模式中，该字母已经被使用(true) vector > vec;//第一个字母匹配，存储其位置//初始化部分 for(int i=0;i >maze[i][j]; if(maze[i][j]==word[0]) vec.push_back(make_pair(i,j)); } //核心程序运行 for(vector >::iterator iter=vec.begin();iter !=vec.end();iter++) { alreadyUseFlag[iter->first][iter->second]=true; flag=find(word,1,maze,ableVisitFlag,alreadyUseFlag,iter->first,iter->second); if(flag) break; else for(int j=1;j<=row;j++) memset(alreadyUseFlag[j],false,sizeof(bool)*(col+2)); } //指针空间释放 for(int i=0;i 3.算法分析
进行分析。题目要求和解决方法如下：
1.搜索算法要满足“前进”和“后退”自适应度。本文采用的是嵌套内循环，在某一级嵌套里，倘若当前某种方向的搜索有效，则将此种方向的值带入下一级嵌套内循环；倘若当前这一级嵌套内循环搜索的方向无效，则搜索下一方向；倘若本次嵌套的所有方向都无效，则上一级嵌套循环开始搜索其他方向。
2.由于访问可能出现越界，本文定义了维度为（row+2，col+2）的二维矩阵ablevisit。初始化时，令中间大小为row*col的空间值为true,代表能访问，其他为false，代表不能访问。大小与ablevisit相同的矩阵chess存储输入字符，注意此处字符并非从头开始存储，而只是存储在中间大小为row*col的空间。也就是说，与ablevisit一一对应。
3.由于一个字符只能使用一次。因此同样定义为维度为（row+2，col+2）的二维矩阵use,初始化全部为0，use的实际使用空间和chess也是一一对应。当chess中某处位置对应的use标志为true,代表这里已经匹配了字符，也就是说，阻止了搜索算法逆向搜索。注意：以起点的坐标遍历的每次，use都需要初始化，而ablevisit不需要。
注：本程序是在上修改，增加自适应度后的版本，并修正了语法和算法错误。相较于源程序更加标准，更加精确。