题解 | 矩阵中的路径

static int gs_flag = 0;

int dfs(int* data, char* matrix, int rows, int cols, int i, int j, char* str,
        int index) {
    if (i < 0 || i >= rows || j < 0 || j >= cols) {
        return 0;
    }

    if (data[i *  cols + j] == 1) {
        return 0;
    }

    char cc = matrix[i *  cols + j];
    if (cc != str[index - 1]) {
        return 0;
    }

    if (index == strlen(str)) {
        gs_flag = 1;
        return 1;
    }

    data[i *  cols + j] = 1;

    dfs(data, matrix, rows, cols, i - 1, j, str, index + 1);
    dfs(data, matrix, rows, cols, i + 1, j, str, index + 1);
    dfs(data, matrix, rows, cols, i, j + 1, str, index + 1);
    dfs(data, matrix, rows, cols, i, j - 1, str, index + 1);

    return 0;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix string字符串
 * @param rows int整型
 * @param cols int整型
 * @param str string字符串
 * @return bool布尔型
 */
bool hasPath(char* matrix, int rows, int cols, char* str ) {
    // write code here
    int i = 0, j = 0;
    int* data = NULL;

    if (strlen(matrix) != rows * cols) {
        return false;
    }

    if (strlen(str) == 0) {
        return false;
    }

    data = (int*) calloc(rows * cols, sizeof(int));

    for (i = 0; i <  rows; i++) {
        for (j = 0; j <  cols; j++) {
            if (matrix[i *  cols + j] == str[0]) {
                memset(data, 0, rows * cols);
                dfs(data, matrix, rows, cols, i, j, str, 1);
            }
        }
    }

    if (data != NULL) {
        free(data);
    }

    if (gs_flag == 1) {
        return true;
    }

    return false;
}