FZU2150* **双源BFS

链接: [link]http://acm.fzu.edu.cn/problem.php?pid=2150
题意：
给你一些二维点坐标，可以抽象为给你一些小正方形格子，绿色小方格 = ‘#’也就是草地， 白色方格子 = ‘.’也就是空地。然后每次有俩个人同时在草地上点火，每次绿色小方格的火只能向草地蔓延，并且每移动一次时间为1s，不能向空地蔓延。问题是：求2个人同时在草地上点火，求烧完整个草地的最小时间，否则输出-1。

思路：先把所有的绿色小方格遍历出来，然后按照题意模拟二个人同时在草地点火。

代码

#include <iostream>
#include <cstring> 
#include <queue>
using namespace std;
const int N = 20;
int n, m, size, res, cnt, kase, res1, flag;
char points[N][N];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}, vis[N][N];

struct node {
  int x, y, step;
}cow[100*N];
//判断是否合法点函数
bool check(int x, int y) {
  if(x >= 0 && y >= 0 && x < n && y < m && !vis[x][y] && points[x][y] == '#') 
    return true;
  return false;
}
//bfs模拟火烧草地情况
void bfs(int xx, int yy) {
  node temp, temq; queue<node> qq;
  cnt = 2, res1 = 0;
  temp.x = cow[xx].x, temp.y = cow[xx].y, temp.step = 0;
  temq.x = cow[yy].x, temq.y = cow[yy].y, temq.step = 0;
  vis[cow[xx].x][cow[xx].y] = 1;vis[cow[yy].x][cow[yy].y] = 1;
  qq.push(temp), qq.push(temq);
  while(!qq.empty()) {
    node old = qq.front();
    qq.pop();
    for(int i = 0; i < 4; i++) {
      node now;
      now.x = dx[i] + old.x, now.y = dy[i] + old.y;
      if(check(now.x, now.y) == true) {
      	now.step = old.step + 1;
      	res1 = now.step;
        vis[now.x][now.y] = 1;
        cnt ++ ;
        qq.push(now);
      }
    }
  }
  if(cnt  == size ) {
    flag = 1;
    res = min(res, res1);
  }
}
//暴力模拟2个人烧所有草地
void work() {
  res = 1e9 + 10, flag = 0;
  cout << "Case " << kase++ << ": " ;
  if(size == 2 || size == 1) {
  	cout << "0" << endl;
  }
  else {
  	for(int i = 0; i < size - 1; i++) {
	    for(int j = i + 1; j < size ; j++) {
	      memset(vis, 0, sizeof vis);
	      bfs(i, j);
	    }
  	}
  	if(flag == 1) cout << res << endl;
	  else cout << "-1" << endl;
  }
}

int main() {
  int T;
  cin >> T; kase = 1;
  while(T -- ) {
    cin >> n >> m;
    size = 0;
    for(int i = 0; i < n; i++) cin >> points[i];
    for(int i = 0; i < n; i++) 
      for(int j = 0; j < m; j++) 
        if(points[i][j] == '#') {
          cow[size].x = i;
          cow[size].y = j;
          cow[size].step = 0;
          size ++;
        }
    work();
  }
  return 0;
}

*转载请注明来源。