广度优先搜索

int** floodFill(int** image, int imageSize, int* imageColSize, 
  int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes){
      *returnSize = imageSize;
      for(int i = 0; i < imageSize; ++i){
          *returnColumuSize[i] = imageSize;
      }
      int oldColor = image[sr][sc];
      if(oldColor == newColor) return image;
      const int dx[4] = {1, 0, -1, 0};
      const int dy[4] = {0, 1, 0, -1};
#if 0
// 广度优先搜索
      int front = 0, rear = 0;
      int queue[imageSize * (*imageColSize)][2];
      queue[rear][0] = sr, queue[rear++][1] = sc;
      while(front < rear){
          int x = queue[front][0], y = queue[front ++][1];
          for(int i = 0; i < 4; ++i){
              int nx = x + dx[i], ny = y + dy[i];
              if(nx >= 0 && nx < imageSize && ny >= 0 && ny < *imageColSize){
                  queue[rear][0] = nx, queue[rear++][1] = ny;
                  image[nx][ny] = newColor;
              }
          }
      }
      return image;
#else 
// 深度优先搜索
    dfs(image, imageSize, imageColSize, sr, sc, oldColor, newColor);
    return iamge;
#endif
  }
  
  void dfs(int **image, int iamgeSize, int *imageColSize, 
          int sr, int sc, int oldColor, int newColor){
      if(image[sr][sc] != oldColor) return ;
      image[sr][sc] = newColor;
      for(int i = 0; i < 4; ++i){
          int nx = sr + dx[i], ny = sc + dy[i];
          if(nx >= 0 && nx < imageSize && ny >= 0 && ny < *imageColSize){
              dfs(image, imageSize, imageColSize, nx, ny, oldColor, newColor);
          }
      }
  }
复制

typedef struct{
    int x;
    int y;
}Queue;


const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
int orangesRotting(int** grid, int gridSize, int* gridColSize){
    int badNum = 0, step = 0;
    Queue *q = (Queue *)malloc(gridSize * (*gridColSize) * sizeof(Queue));
    bzero(q, sizeof(q));
    // 所有的腐烂橘子入队
    for(int i = 0; i < gridSize; ++i){
        for(int j = 0; j < *gridColSize; ++j){
            if(grid[i][j] == 2){
                q[badNum].x = i;
                q[badNum++].y = j;
            }
        }
    }


    int front = 0, rear = badNum;
    while(front < rear){ // 队列不为空则继续循环
        int tempFront = front, tempRear = rear;
        for(int i = tempFront; i < tempRear; ++i){ // 遍历当前队列
            for(int j = 0; j < 4; ++j){ // 四个方向搜索
                int nx = q[i].x + dx[j];
                int ny = q[i].y + dy[j];
                if(nx < 0 || nx >= gridSize || ny < 0 || ny >= *gridColSize) continue;
                if(grid[nx][ny] == 1){
                    grid[nx][ny] = 2;
                    q[badNum].x = nx, q[badNum ++].y = ny;
                }
            }
        }
        front = tempRear, rear = badNum; // 更新队列
        step ++; // 更新答案
    }


     检查是否存在好橘子
    for(int i = 0; i < gridSize; ++i){
        for(int j = 0; j < *gridColSize; ++j){
            if(*(*(grid + i) + j) == 1) return -1;
        }
    }


    return step > 0 ? step - 1 : 0;
}
复制

const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};


int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes)
{
    *returnSize = matSize;
    *returnColumnSizes = matColSize;


    int queue[matSize * (*matColSize)][2];
    int visited[matSize][matColSize[0]];
    bzero(visited, sizeof(visited));
    int rear = 0, front = 0;
    int **res = (int **)malloc(sizeof(int *) * matSize);


    for (int i = 0; i < matSize; i++) {
        res[i] = (int *)malloc(sizeof(int) * matColSize[0]);
        for (int j = 0; j < *matColSize; j++) {
            if (mat[i][j] == 0) {
                res[i][j] = 0;  // 显然0距离最近0的距离为0
                queue[rear][0] = i, queue[rear++][1] = j; // 将元素0的位置加入队列
                visited[i][j] = 2; // 记录遍历状态，为后续剪枝
            }
        }
    }
    // 广度优先遍历
    while (front < rear) {
        int x = queue[front][0], y = queue[front++][1]; // 队首元素出队
        for (int i = 0; i < 4; i++) { // 上下左右四个方向搜索
            int mx = x + dx[i], my = y + dy[i];
            // 新索引的合法性判断
            if (mx < 0 || mx >= matSize || my < 0 || my >= (*matColSize) || visited[mx][my] == 2) {
                continue;
            }
            res[mx][my] = res[x][y] + 1; // 更新结果
            queue[rear][0] = mx, queue[rear++][1] = my; // 将新元素入队
            visited[mx][my] = 2; // 更新索引状态
        }
    }


    return res;
}
复制