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;
}