FZU - 2150 Fire Game bfs+双起点枚举

题意，10*10的地图，有若干块草地“#”，草地可以点燃，并在一秒后点燃相邻的草地。有墙壁‘·‘阻挡。初始可以从任意两点点火。问烧完最短的时间。若烧不完输出-1.

题解：由于100的数据量，直接暴力。枚举两个起点，推入队列，然后bfs。烧完就返回深度，更新一个min值。

坑：（帮同学照bug）

return t.step+1;bfs后没有算上最后一步

ac代码

#define  _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <queue>

#include <vector>

using namespace std;

char map[][];

int vis[][];

int T, n, m, ans, num;

struct Node {

    int i, j, step;

    Node(int i = , int j = , int step = ) :i(i), j(j), step(step) {}

};

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

bool check(int i, int j) {

    if (i< || i >= n || j< || j >= m || vis[i][j] || map[i][j] == '.') return true;

    return false;

}

int bfs(int i, int j, int x, int y) {

    queue<Node>q;

    q.push(Node(i, j, )); q.push(Node(x, y, ));

    vis[i][j] = ; vis[x][y] = ;

    int cnt;

    if (i == x&&j == y) cnt = ;

    else cnt = ;

    while (!q.empty()) {

        Node t = q.front();

        q.pop();

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

            int di = t.i + dir[k][];

            int dj = t.j + dir[k][];

            if (check(di, dj)) continue;

            q.push(Node(di, dj, t.step + ));

            vis[di][dj] = ;

            cnt++;

        }

        if (cnt >= num) {

            //cout << i << ' ' << j << ' ' << x << ' ' << y <<' '<<t.step<< endl;

            return t.step+; }

    }

    return -;

}

int main() {

    scanf("%d", &T);

    for (int t = ; t <= T; t++) {

        ans = (int)1e9; num = ;

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

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

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

            for (int j = ; j<m; j++) if (map[i][j] == '#') num++;

        }

        if (num <= ) { printf("Case %d: %d\n", t, ); continue; }

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

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

                if (map[i][j] != '#') continue;

                for (int x = ; x<n; x++) {

                    for (int y = ; y<m; y++) {

                        if (map[x][y] != '#') continue;

                        memset(vis, , sizeof(vis));

                        int tmp = bfs(i, j, x, y);

                        if (tmp>) ans = min(ans, tmp);

                    }

                }

            }

        }

        if (ans == (int)1e9) ans = -;

        printf("Case %d: %d\n", t, ans);

    }

}