稱號：fzu 2150 Fire Game

：給出一個m*n的圖，‘#’表示草坪，‘ . ’表示空地，然后能夠選擇在隨意的兩個草坪格子點火。火每 1 s會向周圍四個格子擴散，問選擇那兩個點使得燃燒全部的草坪花費時間最小？

分析：這個題目假設考慮技巧的話有點難度，可是鑒于數據范圍比較小，我們能夠暴力枚舉隨意的草坪所在的點，然后兩個點壓進隊列里面BFS。去一個滿足條件的最小值就可以。

順便說一下 fzu 2141 Sub-Bipartite Graph 的思路，比賽的時候沒有做出來。

這個題目想的復雜了，完了之后發現別人用貪心二分染色。每一個點貪心選擇與它相連點的顏色較多的相反的顏色，這樣就能夠了。看來當時真是想復雜了。

AC代碼：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 15;
int dx[5] = {0,0,1,-1};
int dy[5] = {1,-1,0,0};
struct Node
{int x,y;int cnt ;
};
vector<Node> v;
char mp[N][N];
int vis[N][N];
int n,m;
int BFS(Node a,Node b)
{memset(vis,0,sizeof(vis));queue<Node> q;vis[a.x][a.y]  = vis[b.x][b.y] = 1;a.cnt = 0,b.cnt = 0;q.push(a),q.push(b);int ans = 0x3f3f3f3f;int cas = 1;while(!q.empty()){a = q.front();q.pop();//printf("%d %d %d\n",a.x,a.y,a.cnt);ans = a.cnt;for(int i = 0;i<4;i++){b.x = a.x + dx[i];b.y = a.y + dy[i];b.cnt = a.cnt + 1;//printf("B:%d %d %d\n",b.x,b.y,b.cnt);if(b.x>0 && b.y>0 && b.x<=n && b.y<=m && vis[b.x][b.y]==0 && mp[b.x][b.y]=='#'){vis[b.x][b.y] = 1;q.push(b);}}}return ans;
}
void print()
{for(int i=1;i<=n;i++){for(int j = 1;j<=m;j++){printf("%c ",mp[i][j]);}puts("");}
}
int main()
{//freopen("Input.txt","r",stdin);int T;scanf("%d",&T);for(int cas=1;cas<=T;cas++){v.clear();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){getchar();for(int j=1;j<=m;j++){scanf("%c",&mp[i][j]);if(mp[i][j]=='#')v.push_back((Node){i,j,0});}}int ans = 0x3f3f3f3f;for(int i=0;i<v.size();i++){for(int j=i;j<v.size();j++){int tmp = BFS(v[i],v[j]);bool ok = true;for(int k = 1;k<=n;k++){for(int f = 1;f<=m;f++){if(vis[k][f] == 0 && mp[k][f]=='#'){ok = false;break;}}if(ok==false)break;}if(ok){ans = min(ans,tmp);}}}printf("Case %d: ",cas);if(ans == 0x3f3f3f3f)puts("-1");elseprintf("%d\n",ans);}return 0;
}

版權聲明：本文博主原創文章，博客，未經同意不得轉載。

轉載于:https://www.cnblogs.com/zfyouxi/p/4840740.html

總結

以上是生活随笔為你收集整理的fzu 2150 Fire Game 【身手BFS】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。