// 面试题：矩阵中的路径// 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有// 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、// 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入// 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字// 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个// 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。// A B T G// C F C S// J D E H#include 
     
      using namespace std;bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited);bool hasPath(const char* matrix, int rows, int cols, const char* str){    if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr)//负面测试        return false;    bool *visited = new bool[rows * cols];//用来检测某个节点是否已经走过了    memset(visited, 0, rows * cols);//将开辟出来的visitedp[rows * cols]里都设为0    int pathLength = 0;//待检测字符长度变量    for (int row = 0; row < rows; ++row)    {        for (int col = 0; col < cols; ++col)        {            if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited))//遍历每个点，作为起点，开始检测            {                delete[] visited;                return true;            }        }    }    delete[] visited;    return false;}bool hasPathCore(const char* matrix, int rows, int cols, int row,    int col, const char* str, int& pathLength, bool* visited){    if (str[pathLength] == '\0')//递归停止条件一，我经找到最后一个字符了，查找完毕，返回正确        return true;    bool hasPath = false;    if (row >= 0 && row < rows && col >= 0 && col < cols        && matrix[row * cols + col] == str[pathLength]        && !visited[row * cols + col])//这个是我没有走过的节点中，那符合我现在查找的字符A吗    {        ++pathLength;//符合，那找下个字符B        visited[row * cols + col] = true;//这个点在这个起点的时候，我走过了        hasPath = hasPathCore(matrix, rows, cols, row, col - 1,            str, pathLength, visited)            || hasPathCore(matrix, rows, cols, row - 1, col,                str, pathLength, visited)            || hasPathCore(matrix, rows, cols, row, col + 1,                str, pathLength, visited)            || hasPathCore(matrix, rows, cols, row + 1, col,                str, pathLength, visited);//以上下左右节点分别为起点检测字符B        if (!hasPath)//完了走不通        {            --pathLength;//这个节点A以后的没希望了，那我退回一下，继续找A            visited[row * cols + col] = false;//那当我这个点没走过吧        }    }    return hasPath;}// ====================测试代码====================void Test(const char* testName, const char* matrix, int rows, int cols, const char* str, bool expected){    if (testName != nullptr)        printf("%s begins: ", testName);    if (hasPath(matrix, rows, cols, str) == expected)        printf("Passed.\n");    else        printf("FAILED.\n");}//ABTG//CFCS//JDEH//BFCEvoid Test1(){    const char* matrix = "ABTGCFCSJDEH";    const char* str = "BFCE";    Test("Test1", (const char*)matrix, 3, 4, str, true);}//ABCE//SFCS//ADEE//SEEvoid Test2(){    const char* matrix = "ABCESFCSADEE";    const char* str = "SEE";    Test("Test2", (const char*)matrix, 3, 4, str, true);}//ABTG//CFCS//JDEH//ABFBvoid Test3(){    const char* matrix = "ABTGCFCSJDEH";    const char* str = "ABFB";    Test("Test3", (const char*)matrix, 3, 4, str, false);}//ABCEHJIG//SFCSLOPQ//ADEEMNOE//ADIDEJFM//VCEIFGGS//SLHECCEIDEJFGGFIEvoid Test4(){    const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SLHECCEIDEJFGGFIE";    Test("Test4", (const char*)matrix, 5, 8, str, true);}//ABCEHJIG//SFCSLOPQ//ADEEMNOE//ADIDEJFM//VCEIFGGS//SGGFIECVAASABCEHJIGQEMvoid Test5(){    const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SGGFIECVAASABCEHJIGQEM";    Test("Test5", (const char*)matrix, 5, 8, str, true);}//ABCEHJIG//SFCSLOPQ//ADEEMNOE//ADIDEJFM//VCEIFGGS//SGGFIECVAASABCEEJIGOEMvoid Test6(){    const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SGGFIECVAASABCEEJIGOEM";    Test("Test6", (const char*)matrix, 5, 8, str, false);}//ABCEHJIG//SFCSLOPQ//ADEEMNOE//ADIDEJFM//VCEIFGGS//SGGFIECVAASABCEHJIGQEMSvoid Test7(){    const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SGGFIECVAASABCEHJIGQEMS";    Test("Test7", (const char*)matrix, 5, 8, str, false);}//AAAA//AAAA//AAAA//AAAAAAAAAAAAvoid Test8(){    const char* matrix = "AAAAAAAAAAAA";    const char* str = "AAAAAAAAAAAA";    Test("Test8", (const char*)matrix, 3, 4, str, true);}//AAAA//AAAA//AAAA//AAAAAAAAAAAAAvoid Test9(){    const char* matrix = "AAAAAAAAAAAA";    const char* str = "AAAAAAAAAAAAA";    Test("Test9", (const char*)matrix, 3, 4, str, false);}//A//Avoid Test10(){    const char* matrix = "A";    const char* str = "A";    Test("Test10", (const char*)matrix, 1, 1, str, true);}//A//Bvoid Test11(){    const char* matrix = "A";    const char* str = "B";    Test("Test11", (const char*)matrix, 1, 1, str, false);}void Test12(){    Test("Test12", nullptr, 0, 0, nullptr, false);}int main(int argc, char* argv[]){    Test1();    Test2();    Test3();    Test4();    Test5();    Test6();    Test7();    Test8();    Test9();    Test10();    Test11();    Test12();    system("pause");    return 0;}