FOJ 2150 在二维草地上点火烧完所有草最少时间 BFS+图论+容斥

题意：

给定一个平面图 . 为空地（不着火） # 为草

开始可以选1-2个草堆点燃，每隔一秒会把上下左右的草引燃（开始时间为0秒）

问把所有草烧光的最少时间

给定的图中必有草

思路：

纯暴力的话复杂度是 n^8 TLE

我们可以先处理出2个数组

d数组 表示任意点间距离

go[i][j] 表示 在 (i ,j) 所在的联通块 中里 (i ,j) 最远的草的距离

预处理时间为n^4

对于题目中的草其实可以分为

联通块>2 (显然是烧不完的 , ans = -1)

联通块 == 2 ( 每个联通块都要一个火把点燃， 而每个联通块最长时间则是 go[ 该联通块的点 ] , 取个两联通块需要的最长时间即可 复杂度为n^2)

联通块 == 1 ( 我们设 a, b为起点 ，则对于图中的草c，被点燃的时间就是 min(d[a][c], d[b][c]) ，则暴力一下所有草就得到 ab为起点的时间，暴力一下ab就得到正解

复杂度为n^6

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          using namespace std; #define N 12 int f[1000]; int find(int x){return x==f[x] x:f[x] = find(f[x]);} int idx(int x,int y){return x*10+y;} void Union(int x,int y){ int fx = find(x), fy = find(y); if(fx == fy)return ; fx
         
          q; q.push(a); int ans = 0; while(!q.empty()){ node u = q.front(); q.pop(); for(int i = 0;i < 4; i++){ node v = u; v.x += step[i][0]; v.y += step[i][1]; if(!inmap(v) || map[v.x][v.y] == 0 || d[a.x][a.y][v.x][v.y] != -1)continue; d[a.x][a.y][v.x][v.y] = d[a.x][a.y][u.x][u.y]+1; ans = max(ans, d[a.x][a.y][v.x][v.y]); q.push(v); } } return ans; } set
          
           myset;//所有祖先 set
           
            ::iterator p; int go[N][N]; //go[i][j]表示在(i,j)联通块中离(i,j)最远点距离 int main() { int T,Cas = 1; scanf(%d,&T); int i, j, k, l; while(T--){ myset.clear(); memset(d, -1, sizeof(d)); memset(go, -1, sizeof(go)); memset(map, 0, sizeof(map)); scanf(%d %d,&n,&m); for(i=0;i
            
             =n || y<0 || y>=m || map[x][y] == 0)continue; Union(idx(i,j), idx(x,y)); } } } } if(size<=2){printf(Case %d: 0 ,Cas++);continue;} for(i= 0;i
             
              = 3){printf(Case %d: -1 ,Cas++);continue;} bool hehe = myset.size() == 2; int ans = 100000; for(i=0;i