程式語言 - LeetCode - C - 399. Evaluate Division

參考資訊：
https://blog.csdn.net/fuxuemingzhu/article/details/82591165

題目：


解答：

#define MAX_SIZE 128

double dfs(int a, int b, double **q, int *visit)
{
    int c0 = 0;
    double r = 0;

    if (a == b) {
        return 1.0;
    }

    visit[a] = 1;
    for (c0 = 0; c0 < MAX_SIZE; c0++) {
        if ((q[a][c0] > 0) && (visit[c0] == 0)) {
            r = dfs(c0, b, q, visit);
            if (r > 0.0) {
                return r * q[a][c0];
            }
        }
    }

    return -1.0;
}

int str2idx(const char *s)
{
    int c0 = 0;
    static char **q = NULL;


    if (q == NULL) {
        q = malloc(sizeof(char *) * MAX_SIZE);
        memset(q, 0, sizeof(char *) * MAX_SIZE);
    }

    for (c0 = 0; c0 < MAX_SIZE; c0++) {
        if (q[c0] == NULL) {
            break;
        }
        
        if (!strcmp(q[c0], s)) {
            return c0;
        }
    }

    q[c0] = malloc(strlen(s) + 1);
    strcpy(q[c0], s);

    return c0;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
double* calcEquation(
    char ***equations,
    int equationsSize,
    int *equationsColSize,
    double *values,
    int valuesSize,
    char ***queries,
    int queriesSize,
    int *queriesColSize,
    int *returnSize)
{
    int c0 = 0;
    int c1 = 0;
    int *exist = NULL;
    int *visit = NULL;
    double *r = NULL;
    double **q = NULL;

    q = malloc(sizeof(double) * MAX_SIZE);
    for (c0 = 0; c0 < MAX_SIZE; c0++) {
        q[c0] = malloc(sizeof(double) * MAX_SIZE);
        memset(q[c0], 0, sizeof(double) * MAX_SIZE);
    }

    exist = malloc(sizeof(int) * MAX_SIZE);
    memset(exist, 0, sizeof(int) * MAX_SIZE);

    for (c0 = 0; c0 < equationsSize; c0++) {
        int a = str2idx(equations[c0][0]);
        int b = str2idx(equations[c0][1]);

        q[a][b] = values[c0];
        q[b][a] = 1.0 / values[c0];

        exist[a] |= 1;
        exist[b] |= 1;
    }

    r = malloc(sizeof(double) * queriesSize);
    memset(r, 0, sizeof(double) * queriesSize);

    visit = malloc(sizeof(int) * MAX_SIZE);
    for (c0 = 0; c0 < queriesSize; c0++) {
        int a = str2idx(queries[c0][0]);
        int b = str2idx(queries[c0][1]);

        if ((exist[a] && exist[b]) == 0) {
            r[c0] = -1.0;
            continue;
        }

        memset(visit, 0, sizeof(int) * MAX_SIZE);
        r[c0] = dfs(a, b, q, visit);
    }

    *returnSize = queriesSize;
    return r;
}