目录

规则

在一个由大小写字母组成的矩阵中查找一个给定的字符串，这个字符串要求在矩阵中串成一个拐直角弯的相连序列，

形状像贪吃蛇一样，如果矩阵中存在这样的序列则查找成功。

目录结构

src/main.cpp

#include "../include/findstr.h"int main(int argc, char* argv[]){    if(argc !=3)    {        cout<<"argc should is 3, now it is "<
    
     <
    

src/findstr.cpp

#include "../include/findstr.h"using namespace std;StrMatrix::StrMatrix(vector
    
     &vectstr)   {    row = vectstr.size();    if(row>0)    {        col = vectstr[0].length();    }    else         return;    size = row*col;    pchar = new char[size];    pflag= new int[size];    int trow=0;    for (string str :vectstr)    {        for(int j=0; j split(const string &str, string ch = " "){    vector
     
      ret;    int pos = 0;    int start = 0;    while ((pos = str.find(ch, start) )!= string::npos )    {        //cout << "pos:" << pos << endl;        if (pos>start)        ret.push_back(str.substr(start, pos-start));        start = pos+ch.size();    }    if (str.size()>start)    ret.push_back(str.substr(start));    return ret;}int checkPos(int i,int j, int*pos, char ch, int &validnum, StrMatrix &charMat){    if(charMat.notUsed(i,j) && charMat.getchar(i,j) == ch)    {        pos[validnum] = i;        pos[validnum+1] = j;        validnum+=2;    }}int recursion(int i,int j,StrMatrix  &charMat, string curstr){    int ret=1;    int pos[6];    int validnum=0;    checkPos(i,j+1,pos,curstr[0],validnum,charMat);    checkPos(i,j-1,pos,curstr[0],validnum,charMat);    checkPos(i-1,j,pos,curstr[0],validnum,charMat);    checkPos(i+1,j,pos,curstr[0],validnum,charMat);    if(validnum>0 && curstr.length()==1)    {        //cout<<"has find!"<
      
       <
       
        onemat=split(argvone);    StrMatrix charMat(onemat);    charMat.print();    vector
        
         strMatrix=split(argvtwo);    int ret=0;    for (string curstr :strMatrix)    {        //cout<<"curstr:"<
         
          <
         
        
       
      
     
    

include/findstr.h

#include
    
       #include
     
        #include
      
         using namespace std;class StrMatrix{public:    unsigned  row, col, size;       char*pchar;    int*pflag;    StrMatrix(vector
       
        &vectstr);    ~StrMatrix();    void setUsed(unsigned i,unsigned j);    int notUsed(unsigned i,unsigned j);    void clearFlag();    void assignCharArr(vector
        
         &);    char getchar(unsigned i, unsigned j);    void print();};vector
         
           split(const string &str, string ch );int findSingleStr(StrMatrix &charMat, string& curstr);int findStr(string argvone,string argvtwo);
         
        
       
      
     
    

ft/TestCase.cpp

#include 
    
     #include "../include/findstr.h"TEST(FooTest, SingleCharCase){    EXPECT_EQ(findStr("qwer asdf zxcv", "s a d"),0);}TEST(FooTest, multiStrCase){    EXPECT_EQ(findStr("qwer asdf zxcv", "qwsxcv qwedsazxcv rfvcxzaswq"),0);}TEST(FooTest, UseTwiceiSameChar){    EXPECT_EQ(findStr("qwer asdf zxcv", "aa cvc qazxz"),1);}TEST(FooTest, NotSerieschar){    EXPECT_EQ(findStr("qwer asdf zxcv", "qsc asf zxdf qwdf"),1);}
    

ft/makefile

cc = g++ -std=c++11 prom = ../output/ftdeps = ../include/findstr.h obj = ../src/findstr.o  TestCase.oLIBS = -lgtest -lgtest_main -lpthread$(prom): $(obj)    $(cc) $(obj)  $(LIBS) -o $(prom)%.o: %.c $(deps)    $(cc) -c $< -o $@

ftbuild.sh

cd ftmakecd ../outputecho $(pwd)./ft

mainbuild.sh

g++ -std=c++11 -g src/*.cpp -o output/findstr