C语言 | Leetcode C语言题解之第417题太平洋大西洋水流问题

题目：

题解：

static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void bfs(int row, int col, bool ** ocean, const int ** heights, int m, int n) {
    if (ocean[row][col]) {
        return;
    }
    ocean[row][col] = true;
    int * queue = (int *)malloc(sizeof(int) * m * n);
    int head = 0;
    int tail = 0;
    queue[tail++] = row * n + col;
    while (head != tail) {
        int row = queue[head] / n;
        int col = queue[head] % n;
        head++;
        for (int i = 0; i < 4; i++) {
            int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col] && !ocean[newRow][newCol]) {
                ocean[newRow][newCol] = true;
                queue[tail++] = newRow * n + newCol;
            }
        }
    }
    free(queue);
}

int** pacificAtlantic(int** heights, int heightsSize, int* heightsColSize, int* returnSize, int** returnColumnSizes){
        int m = heightsSize;
        int n = heightsColSize[0];
        bool ** pacific = (bool **)malloc(sizeof(bool *) * m);
        bool ** atlantic = (bool **)malloc(sizeof(bool *) * m);
        for (int i = 0; i < m; i++) {
            pacific[i] = (bool *)malloc(sizeof(bool) * n);
            atlantic[i] = (bool *)malloc(sizeof(bool) * n);
            memset(pacific[i], 0, sizeof(bool) * n);
            memset(atlantic[i], 0, sizeof(bool) * n);
        }

        for (int i = 0; i < m; i++) {
            bfs(i, 0, pacific, heights, m, n);
        }
        for (int j = 1; j < n; j++) {
            bfs(0, j, pacific, heights, m, n);
        }
        for (int i = 0; i < m; i++) {
            bfs(i, n - 1, atlantic, heights, m, n);
        }
        for (int j = 0; j < n - 1; j++) {
            bfs(m - 1, j, atlantic, heights, m, n);
        }
        int ** result = (int **)malloc(sizeof(int *) * m * n);
        *returnColumnSizes = (int *)malloc(sizeof(int) * m * n);
        int pos = 0;
        for (int i = 0; i < m * n; i++) {
            result[i] = (int *)malloc(sizeof(int) * 2);
            (*returnColumnSizes)[i] = 2;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result[pos][0] = i;
                    result[pos][1] = j;
                    pos++;
                }
            }
            free(pacific[i]);
            free(atlantic[i]);
        }
        free(pacific);
        free(atlantic);
        *returnSize = pos;
        return result;
}