FZU 2150 Fire Game --两点同步搜索

枚举两点，然后同步BFS，看代码吧，很容易懂的。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#include <queue>

#define Mod 1000000007

using namespace std;

struct Point

{

    int x,y;

    int step;

}S;

char mp[][];

int vis[][];

int n,m;

int lef;

int dx[] = {,,,-};

int dy[] = {,-,,};

queue<Point> que;

bool OK(int nx,int ny)

{

    if(nx < n && nx >=  && ny < m && ny >= )

        return true;

    return false;

}

int BFS()

{

    int maxi = ;

    while(!que.empty())  //同步搜索

    {

        int SIZE = que.size();

        while(SIZE--)

        {

            Point tmp = que.front();

            que.pop();

            int nx = tmp.x;

            int ny = tmp.y;

            int step = tmp.step;

            maxi = max(maxi,step);

            Point now;

            for(int k=;k<;k++)

            {

                int kx = nx + dx[k];

                int ky = ny + dy[k];

                if(!OK(kx,ky) || vis[kx][ky])

                    continue;

                if(mp[kx][ky] == '#')

                {

                    vis[kx][ky] = ;

                    now.x = kx;

                    now.y = ky;

                    now.step = step+;

                    que.push(now);

                    lef--;

                }

            }

        }

    }

    if(lef == )

        return maxi;

    else

        return -;

}

int main()

{

    int t,cs = ,i,j,k,h;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        int cnt = ;

        for(i=;i<n;i++)

        {

            scanf("%s",mp[i]);

            for(j=;j<m;j++)

                if(mp[i][j] == '#')

                    cnt++;

        }

        int flag = ;

        int tag = Mod;

        for(i=;i<n;i++)   //第一个点

        {

            for(j=;j<m;j++)

            {

                if(mp[i][j] == '#')

                {

                    for(k=i;k<n;k++)   //第二个点

                    {

                        for(h=(k==i?j:);h<m;h++)

                        {

                            if(mp[k][h] == '#')

                            {

                                memset(vis,,sizeof(vis));

                                S.x = i,S.y = j,S.step = ;

                                que.push(S);

                                lef = cnt-;

                                vis[i][j] = ;

                                if(!(i==k&&j==h))

                                {

                                    S.x = k,S.y = h,S.step = ;

                                    que.push(S);

                                    vis[k][h] = ;

                                    lef--;

                                }

                                int res = BFS();

                                if(res != -)

                                {

                                    flag = ;

                                    tag = min(tag,res);

                                }

                            }

                        }

                    }

                }

            }

        }

        if(flag)

            printf("Case %d: %d\n",cs++,tag);

        else

            printf("Case %d: -1\n",cs++);

    }

    return ;

}