寻找矩阵中的指定路径

给定一个矩阵和一个要找的字符串，如果有的话找出矩阵中的字符串路径。

测试用例

功能测试：在多行多列的矩阵中存在或者不存在路径

边界值测试：矩阵只有一行或一列；矩阵和路径中的所有字母都是相同的

特殊输入测试：输入nullptr指针

​

#include<iostream>
#include<string.h>

using namespace std;

bool haspathCore(char* matrix,int row,int colunm,int rows,int colunms,bool* visited,int pathlength,char* str)
{
    if(str[pathlength]=='\0')
        return true;

    bool haspath=false;
    if(row>=0&&row<rows&&colunm>=0&&colunm<colunms&&matrix[row*rows+colunm]==str[pathlength]&&visited[row*rows+colunm]==0)
    {
        ++pathlength;
        haspath=haspathCore(matrix,row-1,colunm,rows,colunms,visited,pathlength,str)||
                haspathCore(matrix,row+1,colunm,rows,colunms,visited,pathlength,str)||
                haspathCore(matrix,row,colunm-1,rows,colunms,visited,pathlength,str)||
                haspathCore(matrix,row,colunm+1,rows,colunms,visited,pathlength,str);

        if(!haspath)
        {
            --pathlength;
            visited[row*rows+colunm]=0;
        }
    }

    return haspath;
}

bool haspath(char *matrix,int colunms,int rows,char *str)
{
    if(matrix==nullptr||colunms<1||rows<1||str==nullptr)
        return false;

    bool *visited=new bool[colunms*rows];
    memset(visited,0,rows*colunms);
    int pathlength=0;

    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<colunms;j++)
        {
            if(haspathCore(matrix,i,j,rows,colunms,visited,pathlength,str))
                return true;
        }
    }

    delete []visited;

    return false;
}

int main()
{
    char matrix[]={'a','b','t','g',
                   'c','f','c','s',
                   'j','d','e','h'};
    char str[]="abfb";

    if(haspath(matrix,4,3,str))
        cout<<"Found"<<endl;
    else
        cout<<"Not Found"<<endl;

    return 0;
}

[点击并拖拽以移动]
​

在这个矩阵中可以任意选择一个起点，如果该字符ch等于第str字符串中第i个字符，那么就在ch的上下左右寻找与str的第i+1个字符相等的字符，如果找到就基于第i+1个字符寻找下一个字符，如果没找到就退回一步，重新找新的方向，直到将矩阵每个值当作起点找过一遍还是没找到就false结束，或者当str找到结尾字符'\0'是以true结束。

由于不能重复走走过的格子，所以需要一个数组记录是否已经走过这个格子。这题是根据回溯法的递归特性，路径可以被看做是一个栈，符合就压入，不符合就弹出，回到上一个再找。