本文共 4312 字，大约阅读时间需要 14 分钟。

���������12���������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������

���������������������������������DFS������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������������

������������

#include 
   
    
#include 
    
     
using namespace std;
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) {
        if (!visited[row * cols + col]) {
            if (matrix[row * cols + col] == str[pathLength]) {
                visited[row * cols + col] = true;
                pathLength++;
                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);
                if (!hasPath) {
                    pathLength--;
                    visited[row * cols + col] = false;
                }
            }
        }
    }
    return hasPath;
}
bool hasPath(const char* matrix, int rows, int cols, const char* str) {
    if (matrix == nullptr || rows <= 0 || cols <= 0 || str == nullptr) {
        return false;
    }
    bool* visited = new bool[rows * cols];
    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)) {
                return true;
            }
        }
    }
    delete[] visited;
    return false;
}
void Test(const char* testName, const char* matrix, int rows, int cols, const char* str, bool expected) {
    if (hasPath(matrix, rows, cols, str) == expected) {
        printf("Passed.\n");
    } else {
        printf("FAILED.\n");
    }
}
void Test1() {
    const char* matrix = "ABTGCFCSJDEH";
    const char* str = "BFCE";
    Test("Test1", (const char*)matrix, 3, 4, str, true);
}
void Test2() {
    const char* matrix = "ABCESFCSADEE";
    const char* str = "SEE";
    Test("Test2", (const char*)matrix, 3, 4, str, true);
}
int main() {
    Test1();
    Test2();
    return 0;
}
    
   

������������

���������������DFS���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������