【FZU - 2150】Fire Game（bfs）

佚名 5年前 (2019-07-02) 算法 1331人围观抢沙发百度已收录

--> Fire Game

直接写中文了

Descriptions:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

两个熊孩子在n*m的平地上放火玩，#表示草，两个熊孩子分别选一个#格子点火，火可以向上向下向左向右在有草的格子蔓延，点火的地方时间为0，蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出-1。

Input

第一行，输入一个T,表示有T组测试数据。每组数据由一个n，m分别表示行列

1 <= T <=100, 1 <= n <=10, 1 <= m <=10

Output

输出最少需要的时间

Sample Input

4
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#

Sample Output

Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2

题目链接：

https://vjudge.net/problem/FZU-2150

感觉还是有一定难度的，肯定是要从两个地方开始dfs的，这两个地方一定是干草，同时这两个地方可以重叠，那么就直接把所有的干草全部列举出来，每次取两个去dfs，然后取这些dfs的最小值即可，具体操作看代码

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define ME0(x) memset(x,0,sizeof(x))
using namespace std;
int T,n,m,total,cnt;
char mp[15][15];//原始地图
int vis[15][15];//记录是否烧过
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//方向
struct node
{
    int x,y;//横纵坐标
    int step;//步数
};
node now,next;
node a[15*15];//干草坐标
bool judge()//判断草地是否全部烧完
{
    for(int i=0; i<total; i++)
        if(!vis[a[i].x][a[i].y])
            return false;
    return true;
}
int bfs(node a,node b)
{
    int steps=0;//初始步数为0
    ME0(vis);
    queue<node>q;
    q.push(a),q.push(b);
    vis[a.x][a.y]=1,vis[b.x][b.y]=1;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0; i<4; i++)//分4个方向测试
        {
            next.x=now.x+dt[i][0];
            next.y=now.y+dt[i][1];
            next.step=now.step+1;
            //是否满足条件
            if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]=='#'&&!vis[next.x][next.y])
            {
                vis[next.x][next.y]=1;
                steps=max(steps,next.step);
                q.push(next);
            }
        }
    }
    if(judge())//判断
        return steps;
    else
        return INF;
}
int main()
{
    cnt=1;//第几组测试数据
    cin>>T;
    while(T--)
    {
        total=0;//有多少干草
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]=='#')//把干草存入数组
                {
                    a[total].x=i;
                    a[total].y=j;
                    a[total++].step=0;
                }
            }
        }
        int ans=INF;
        for(int i=0; i<total; i++)
        {
            for(int j=i; j<total; j++)
            {
                ans=min(bfs(a[i],a[j]),ans);//每次都取步数最小的值
            }
        }
//        for(int i=0; i<total; i++)
//            cout<<a[i].x<<" "<<a[i].y<<endl;
        printf("Case %d: ",cnt++);
        if(ans==INF)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
    }
}