fzu 2150 Fire Game 【技巧BFS】

「爱情、让人受尽委屈。」 2022-08-14 01:45 5阅读 0赞

题目：fzu[ 2150 Fire Game][2150 Fire Game]

题意：给出一个m\*n的图，‘\#’表示草坪，‘ . ’表示空地，然后可以选择在任意的两个草坪格子点火，火每 1 s会向周围四个格子扩散，问选择那两个点使得燃烧所有的草坪花费时间最小？

分析：这个题目如果考虑技巧的话有点难度，但是鉴于数据范围比较小，我们可以暴力枚举任意的草坪所在的点，然后两个点压进队列里面BFS，去一个满足条件的最小值即可。

顺便说一下 fzu 2141 Sub-Bipartite Graph 的思路，比赛的时候没有做出来。

这个题目想的复杂了，完了之后发现别人用贪心二分染色，每个点贪心选择与它相连点的颜色较多的相反的颜色，这样就可以了。看来当时真是想复杂了。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <queue>
    using namespace std;
    typedef long long LL;
    const int N = 15;
    int dx[5] = {0,0,1,-1};
    int dy[5] = {1,-1,0,0};
    struct Node
    {
        int x,y;
        int cnt ;
    };
    vector<Node> v;
    char mp[N][N];
    int vis[N][N];
    int n,m;
    int BFS(Node a,Node b)
    {
        memset(vis,0,sizeof(vis));
        queue<Node> q;
        vis[a.x][a.y]  = vis[b.x][b.y] = 1;
        a.cnt = 0,b.cnt = 0;
        q.push(a),q.push(b);
        int ans = 0x3f3f3f3f;
        int cas = 1;
        while(!q.empty())
        {
            a = q.front();
            q.pop();
            //printf("%d %d %d\n",a.x,a.y,a.cnt);
            ans = a.cnt;
            for(int i = 0;i<4;i++)
            {
                b.x = a.x + dx[i];
                b.y = a.y + dy[i];
                b.cnt = a.cnt + 1;
                //printf("B:%d %d %d\n",b.x,b.y,b.cnt);
                if(b.x>0 && b.y>0 && b.x<=n && b.y<=m && vis[b.x][b.y]==0 && mp[b.x][b.y]=='#')
                {
                    vis[b.x][b.y] = 1;
                    q.push(b);
                }
            }
        }
        return ans;
    }
    void print()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
            {
                printf("%c ",mp[i][j]);
            }
            puts("");
        }
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            v.clear();
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                getchar();
                for(int j=1;j<=m;j++){
                    scanf("%c",&mp[i][j]);
                    if(mp[i][j]=='#')
                        v.push_back((Node){i,j,0});
                }
            }
            int ans = 0x3f3f3f3f;
            for(int i=0;i<v.size();i++)
            {
                for(int j=i;j<v.size();j++)
                {
                    int tmp = BFS(v[i],v[j]);
                    bool ok = true;
                    for(int k = 1;k<=n;k++)
                    {
                        for(int f = 1;f<=m;f++)
                        {
                            if(vis[k][f] == 0 && mp[k][f]=='#')
                            {
                                ok = false;
                                break;
                            }
                        }
                        if(ok==false)
                            break;
                    }
                    if(ok)
                    {
                        ans = min(ans,tmp);
                    }
                }
            }
            printf("Case %d: ",cas);
            if(ans == 0x3f3f3f3f)
                puts("-1");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

[2150 Fire Game]: http://acm.fzu.edu.cn/problem.php?pid=2150