主要是通过这道题目思考了很多关于树，图的直径，中心等问题。
以下内容跟本题解法弱相关。
说到树的直径（树上最远点对），基本上就是最经典的树形dp了，但是紫书上还介绍了一种很不错的方法，两遍dfs。详见紫书p282。
网上找的详解及证明：http://blog.sina.com.cn/s/blog_dbe928200101cm5t.html
我觉得图应该也是一样的道理。
如果只点一把火的话，只用求下联通快的个数，算出直径，就可以输出答案了。
但是点两把火，求出来的直径就没什么用了，燃烧时间是不能用直径算出来的。
所以只好枚举了。反正数据也小。
图的绝对中心：我记得自己在很久很久以前在cf上做过类似的题目的。
http://blog.csdn.net/crazy_ac/article/details/8816877
代码
#include<stdio.h> #include<algorithm> #include<string.h> #include<queue> using namespace std; const int maxn = 10; const int inf = 0x3f3f3f3f; int n,m; char MAP[maxn][maxn]; int vis[maxn][maxn]; int N; int dr[4]={-1, 0, 1, 0}; int dc[4]={ 0, 1, 0,-1}; bool ok(int r,int c) { return 0<=r&&r<n&&0<=c&&c<m; } int bfs(int S1,int S2) { memset(vis,inf,sizeof(vis)); queue<int>q; q.push(S1); q.push(S2); vis[S1/m][S1%m]=0; vis[S2/m][S2%m]=0; while(!q.empty()) { int now = q.front(); q.pop(); int r = now/m; int c = now%m; for(int i=0;i<4;i++) { int rr = r+dr[i]; int cc = c+dc[i]; if(ok(rr,cc)&&vis[rr][cc]==inf&&MAP[rr][cc]=='#') { vis[rr][cc]=vis[r][c]+1; q.push(rr*m+cc); } } } int ret=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(MAP[i][j]=='#') ret=max(ret,vis[i][j]); return ret; } int solve() { scanf("%d %d",&n,&m); N = n*m; for(int i=0;i<n;i++) scanf("%s",MAP[i]); int ans = inf; for(int i=0;i<N;i++) if(MAP[i/m][i%m]=='#') for(int j=i;j<N;j++) if(MAP[j/m][j%m]=='#') ans=min(ans,bfs(i,j)); if(ans==inf) return 0*puts("-1"); else return 0*printf("%d\n",ans); } int main() { int T; scanf("%d",&T); for(int t=1;t<=T;t++) { printf("Case %d: ",t); solve(); } return 0; }