FZU 2150 Fire Game (two points BFS)

题意: Two bear children set fire on the n*m ​​flat, #表示草, two bear children choose one # lattice ignition, the fire can go up and down Left to right spread in the grassy grid, the ignition time is 0, and the time to spread to the next grid is increased by one. The minimum time required to burn all the grass. If you can't burn out the output -1.

思维: The first feeling is that DFS is looking for a connected block, but it doesn't feel right when you think about it. Require minimum time, or BFS, first enumerate two points, if it is #, put these two points into the queue, then expand, each time bfs the last time to find the longest burning time, and then every time Take the minimum value after enumeration.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn=200005;
const double eps=1e-8;
const double PI = acos(-1.0);
struct node
{
    int x,y;
    node(int x,int y):x(x),y(y) {}
    node() {}
};
char g[15][15];
node s1,s2;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int vis[15][15],step[15][15];
    int n,m;
int bfs()
{
    queue<node> q;
    q.push(s1);
    q.push(s2);
    memset(vis,0,sizeof(vis));
    memset(step,inf,sizeof(step));
    step[s1.x][s1.y]=0;
    step[s2.x][s2.y]=0;
    vis[s1.x][s1.y]=1;
    vis[s2.x][s2.y]=1;
    while(!q.empty())
    {
        node f=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
                int x=f.x+dx[i];
                int y=f.y+dy[i];
                if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&g[x][y]=='#')
                {
                    q.push(node(x,y));
                    step[x][y]=step[f.x][f.y]+1;
                    vis[x][y]=1;
                }
        }
    }
    int maxx=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='#')
            {
                maxx=max(maxx,step[i][j]);
            }
        }
    }
    return maxx;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t,cas=0;
    cin>>t;

    while(t--)
    {
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>g[i][j];
            }
        }
        int ans=inf;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(g[i][j]=='#')
                {
                    s1.x=i,s1.y=j;
                    for(int ii=0; ii<n; ii++)
                    {
                        for(int jj=0; jj<m; jj++)
                        {
                            if(g[ii][jj]=='#')
                            {
                                s2.x=ii,s2.y=jj;
                                int tmp=bfs();
                                ans=min(tmp,ans);
                            }
                        }
                    }
                }
            }
        }
        cout<<"Case "<<++cas<<": ";
        if(ans==inf)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}