FZU2150(双起点bfs->多起点)

题目大意：
给出一个height*width的图，'#'表示草坪，'.'表示空地，然后可以选择在任意的两个草坪格子点火，火每 1 s会向周围四个格子扩散，问选择那两个点使得燃烧所有的草坪花费时间最小？
大致思路：
重点是和单起点bfs差不多，唯一不同的就是在刚开始入队的时候将两个起点都入队。可以说是对两个不同根节点的树进行搜索吧(两棵树根节点可相同可不同，枝叶可交叉可不交叉)，主要思路就是这个样子喽，剩下的细节就看个人怎么处理了。同样也可以类比到多起点的搜索。而且如果单纯的暴力枚举的话会计算大量的重复所以可以增加一个dat数组讲草的位置保存下来，进行一些优化。(本人对图的建坐标方式可能恰好相反，见谅!)。

这是我的代码运行结果（前一次写的TLE了(小声

#include <bits/stdc++.h>
using namespace std;
int x,y;
const int MAX = 15;
int dir[][2] = {{-1,0},{0,-1},{1,0},{0,1}};
char vis[MAX][MAX],cur[MAX][MAX]; 
int path[MAX][MAX];     //这个二维数组记录对草对两个起点的最大距离(也就是火烧到此处的时间
struct node{
    int x,y;
    node(int xx=0,int yy=0):
        x(xx),y(yy){}
};
#define check(dx,dy) (0<=dx && dx<x && 0<=dy && dy<y)
vector dat;   //这个保存草的位置
int bfs(node fir,node sec)
{
    memset(path,0,sizeof path);
    memcpy(cur,vis,sizeof vis);
    queue que;
    que.push(fir),que.push(sec);   //两个结点同时入队
    cur[fir.y][fir.x] = '.';cur[sec.y][sec.x] = '.';
    while (!que.empty())
    {
        node tmp = que.front(); que.pop();
        for (int i=0;i<4;i++)
        {
            int dx = tmp.x+dir[i][0],dy = tmp.y+dir[i][1];
            if (check(dx,dy) && '#'==cur[dy][dx])
            {
                que.push(node(dx,dy));
                path[dy][dx] = path[tmp.y][tmp.x] + 1;
                cur[dy][dx] = '.';
            }
        }        
    }
    int res = -0x3f3f3f3f;
    for (int i=0;i<y;i++)
        for (int j=0;j<x;j++)
        {
            if (path[i][j]>res)
                res = path[i][j];
            if ('#'==cur[i][j])
                return -1;   //如果发现草没有烧完，就返回-1，否则返回时间
        }
    return res;
}
int main()
{
    int t;
    while (cin >> t){
        int count = 0;
        while (t--){
            cin >> y >> x;
            dat.clear();
            for (int i=0;i<y;i++)
            {
                scanf("%s",vis[i]);
                for (int j=0;j<x;j++)
                    if ('#'==vis[i][j])
                        dat.push_back(node(j,i));
            }
            int ans = 0x3f3f3f3f;  //枚举
            for (int i=0;i<dat.size();i++)
                for (int j=i;j<dat.size();j++)
                {
                    int tmp = bfs(dat[i],dat[j]);
                    if (-1==tmp)
                        continue;
                    if (tmp<ans)
                        ans = tmp;
                }
            if (0x3f3f3f3f==ans)
                ans = -1;
            cout << "Case " << ++count << ": " << ans << endl;
        }
    }
    return 0;
}