题解 | #矩阵中的路径#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix char字符型二维数组
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @param word string字符串
 * @return bool布尔型
 */

static int row, col, len, k;

void dfs(char** matrix, char* word, int i, int j) {
    char temp = matrix[i][j];
    matrix[i][j] = '.';
    k++;
    if (k == len) {
        return;
    }
    if (i - 1 >= 0 && matrix[i - 1][j] == word[k] && k < len) {
        dfs(matrix, word, i - 1, j);
    }
    if (j - 1 >= 0 && matrix[i][j - 1] == word[k] && k < len) {
        dfs(matrix, word, i, j - 1);
    }
    if (i + 1 < row && matrix[i + 1][j] == word[k] && k < len) {
        dfs(matrix, word, i + 1, j);
    }
    if (j + 1 < col && matrix[i][j + 1] == word[k] && k < len) {
        dfs(matrix, word, i, j + 1);
    }
    if (k == len) {
        return;
    }
    k--;
    matrix[i][j] = temp;
}

bool hasPath(char** matrix, int matrixRowLen, int* matrixColLen, char* word ) {
    // write code here
    if(word==NULL){
        return true;
    }
    if(matrixRowLen==0||*matrixColLen==0){
        return false;
    }
    row = matrixRowLen;
    col = *matrixColLen;
    len = strlen(word);
    int i, j;
    k = 0;
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            if (matrix[i][j] == word[k]) {
                dfs(matrix, word, i, j);
                if (k == len)return true;
            }
        }
    }
    return false;
}