称号：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;
}版权声明：本文博主原创文章，博客，未经同意不得转载。
