通过“溟痕”理解多源BFS

最近打舟肉鸽溟痕关卡“蔓延”时，看到溟痕扩散的方式感觉有点似曾相识，因此有想到如下问题。

我们假设关卡地板为m*n的网格grid，每个单元格可能存在以下值及其对应状态：

• 值为0代表特殊地块，溟痕无法扩散至该地形上
• 值为1代表干净地块（即未被扩散）
• 值为2代表溟痕地块（即已被扩散）

每过12秒，溟痕会向所在单元格周围四个方向上的相邻单元格扩散。编写算法返回直到grim中不存在干净地块为止所需经过的最小时间。若不可能，则返回-1。

备注：PRTS Wiki中关于溟痕扩散机制的解释

溟痕会向四个方向同时扩散，其扩散方式类似于上一篇“岛屿最大面积问题”中BFS的遍历方式。在“蔓延”关卡中，初始状态下并不存在溟痕地块，仅当溟痕怪通过其自身机制在其所处地块上生成溟痕后，关卡中方才存在第一块溟痕，尔后该溟痕会根据BFS思想向地图中其余地块扩散溟痕。

但在部分关卡（如SN-EX-6）中，初始状态下即存在多块溟痕地块，这些地块会同时基于BFS对周围地块进行溟痕扩散，此即多源BFS。在扩散过程中，为了实时统计场上是否仍存在干净地块，需要在扩散前确定干净地块的数量。同时，由于BFS基于队列运行，所有溟痕地块在进行扩散前需要先入队，并在置于队首时方才进行扩散并出队，因此可以通过该过程对溟痕地块总数进行统计，从而确定该批次即将扩散的溟痕地块总数。每有一个元素入队，则溟痕地块的数量较先前多一块。初次进行溟痕扩散操作时，地块及队列的状态为

在队列中仍存在元素时，溟痕地块在扩散过程中若接触到某方向相邻的干净地块，则场上存在的干净地块相应地少一块，同时被扩散的新溟痕地块入队，直至队列被清空（即溟痕地块均扩散完毕且不再有新的溟痕地块生成）。因此，第二次进行溟痕扩散操作时，地块及队列的状态为

最终地块与队列的状态为

值得注意的是，由于每过12秒溟痕所进行的扩散是同时进行的，因此仅在当前批次（即当前层）的溟痕均扩散完毕后，方才将所需时间增加12秒，并进行新入队的溟痕地块的扩散行动。

首先确认地图中存在的干净地块与溟痕地块的数目，并建立用于溟痕扩散的队列

int row = grid.size();
int col = grid[0].size();
queue<pair<int, int>> que;
vector<vector<int>> visited(row, vector<int>(col, 0));
int clean = 0;
int sealed = 0;
for(int i = 0;i < row;i++){
  for(int j = 0;j < col;j++){
    if(grid[i][j] == 2){
      que.push(make_pair(i, j));
      sealed++;
    }
    else if(grid[i][j] == 1){
      clean++;
    }
  }
}

统计完毕后，此时若地图中干净地块与溟痕地块数目均仍为0（即全为特殊地块），则溟痕无法进行扩散，直接返回0

if(sealed == 0 && clean == 0){
  return 0;
}

根据队列开始进行溟痕扩散前，对所需时间进行初始化

#define TIME 12
int time = -TIME;

尔后开始向四个方向进行溟痕扩散，且在队列非空或未接触到边界前该过程会在相应方向上持续

while(!que.empty()){
  int size = que.size();  //队列长度，即当前待扩散的溟痕地块数目
  for(int i = 0;i < size;i++){
    int x = que.front().first;
    int y = que.front().second;
    que.pop();
    //向下扩散
    if(x + 1 < row){
      if(grid[x + 1][y] == 1){
        grid[x + 1][y] = 2;
        clean--;
        que.push(make_pair(x + 1, y));  //新溟痕地块入队
      }
    }
    //向上扩散
    if(x - 1 >= 0){
      if(grid[x - 1][y] == 1){
        grid[x - 1][y] = 2;
        clean--;
        que.push(make_pair(x - 1, y));  //新溟痕地块入队
      }
    }
    //向右扩散
    if(y + 1 < col){
      if(grid[x][y + 1] == 1){
        grid[x][y + 1] = 2;
        clean--;
        que.push(make_pair(x, y + 1));  //新溟痕地块入队
      }
    }
    //向左扩散
    if(y - 1 >= 0){
      if(grid[x][y - 1] == 1){
        grid[x][y - 1] = 2;
        clean--;
        que.push(make_pair(x, y - 1));  //新溟痕地块入队
      }
    }
  }
  time += TIME;  //仅在当前队列清空后，同一层的溟痕均扩散完毕，方才增长时间
}

队列清空后，若场上不再存在干净地块，则返回溟痕扩散所需总时间，否则返回-1

if(clean == 0){
  return time;
}
return -1;

对上述内容进行整合后，完整代码为

#define TIME 12

class Solution{
public:
  int floorsSealing(vector<vector<int>>& grid){
    int row = grid.size();
    int col = grid[0].size();
    queue<pair<int, int>> que;
    vector<vector<int>> visited(row, vector<int>(col, 0));
    int clean = 0;
    int sealed = 0;
    for(int i = 0;i < row;i++){
      for(int j = 0;j < col;j++){
        if(grid[i][j] == 2){
          que.push(make_pair(i, j));
          sealed++;
        }
        else if(grid[i][j] == 1){
          clean++;
        }
      }
    }
    if(sealed == 0 && clean == 0){
      return 0;
    }
    int time = -TIME;
    while(!que.empty()){
      int size = que.size();  //队列长度，即当前待扩散的溟痕地块数目
      for(int i = 0;i < size;i++){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        //向下扩散
        if(x + 1 < row){
          if(grid[x + 1][y] == 1){
            grid[x + 1][y] = 2;
            clean--;
            que.push(make_pair(x + 1, y));  //新溟痕地块入队
          }
        }
        //向上扩散
        if(x - 1 >= 0){
          if(grid[x - 1][y] == 1){
            grid[x - 1][y] = 2;
            clean--;
            que.push(make_pair(x - 1, y));  //新溟痕地块入队
          }
        }
        //向右扩散
        if(y + 1 < col){
          if(grid[x][y + 1] == 1){
            grid[x][y + 1] = 2;
            clean--;
            que.push(make_pair(x, y + 1));  //新溟痕地块入队
          }
        }
        //向左扩散
        if(y - 1 >= 0){
          if(grid[x][y - 1] == 1){
            grid[x][y - 1] = 2;
            clean--;
            que.push(make_pair(x, y - 1));  //新溟痕地块入队
          }
        }
      }
      time += TIME;  //仅在当前队列清空后，同一层的溟痕均扩散完毕，方才增长时间
    }
    if (clean == 0){
      return time;
    }
    return -1;
  }
};

Python下代码为

class Solution:
  def floorsSealing(self, grid: List[List[int]]) -> int:
    row, col, time = len(grid), len(grid[0]), 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = []
    #溟痕地块入队
    for i in range(row):
      for j in range(col):
        if grid[i][j] == 2:
          queue.append((i, j, time))
    #BFS
    while queue:
      i, j, time = queue.pop(0)
      for di, dj in directions:
        if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:
          grid[i + di][j + dj] = 2
          queue.append((i + di, j + dj, time + 12))
    for row in grid:
      if 1 in row: return -1

    return time