第三部分：题目分析与标准代码

1. 算法思路

• 多源 BFS：
  • 题目可能有多个起火点 F。我们需要把所有 F 点都作为起点，在 BFS 初始化时全部加入队列，并将它们的距离设为 0。
  • 这样可以模拟“多处同时起火”的扩散效果。
• 状态记录：
  • 使用 dist[N][M] 数组记录到达每个点的时间。
  • 初始化为 -1 代表未访问。
• 终止条件：
  • 当 BFS 第一次访问到字符 C 时，当前的距离即为最短时间，直接输出并结束程序。
  • 如果队列空了还没访问到 C，说明不可达，输出 Safe。

2. 复杂度分析

• 时间复杂度：$O(N \times M)$。每个格子最多进队一次。对于 $1000 \times 1000$ 的数据，运算量约 $10^6$，远小于 1 秒限时。
• 空间复杂度：$O(N \times M)$，用于存储地图和距离数组。

3. 标准代码 (C++14)

/**
 * 题目：火烧连营 (Fire at Red Cliffs)
 * 难度：GESP 6级
 * 算法：多源 BFS
 */

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

// 坐标结构体
struct Point {
    int x, y;
};

// 方向数组：上 下 左 右
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

const int MAXN = 1005;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN]; // 记录时间，-1表示未访问

int main() {
    // 提升 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    queue<Point> q;
    int endX = -1, endY = -1;

    // 1. 读入并初始化
    for (int i = 0; i < N; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < M; ++j) {
            grid[i][j] = row[j];
            dist[i][j] = -1; // 默认未访问

            if (grid[i][j] == 'F') {
                // 起火点入队，时间为 0
                q.push({i, j});
                dist[i][j] = 0;
            } else if (grid[i][j] == 'C') {
                // 记录终点坐标
                endX = i;
                endY = j;
            }
        }
    }

    // 2. BFS 主循环
    while (!q.empty()) {
        Point curr = q.front();
        q.pop();

        // 如果当前取出的点是终点 C
        if (curr.x == endX && curr.y == endY) {
            cout << dist[curr.x][curr.y] << endl;
            return 0;
        }

        // 尝试向四个方向扩散
        for (int k = 0; k < 4; ++k) {
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];

            // 越界检查
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                // 如果是战船(#)或终点(C)，且未被引燃过
                // 注意：水(.)不能走
                if (grid[nx][ny] != '.' && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[curr.x][curr.y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    // 3. 无法到达
    cout << "Safe" << endl;

    return 0;
}

第四部分：数据生成器

这是修正后的数据生成器，确保生成的测试点覆盖样例、多源起火、迷宫绕路、无解等情况。

/**
 * GESP 6级 [火烧连营] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Point { int x, y; };
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 标准解法生成 .out
string solve(int N, int M, const vector<string>& grid) {
    vector<vector<int>> d(N, vector<int>(M, -1));
    queue<Point> q;
    int endX = -1, endY = -1;

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(grid[i][j] == 'F') {
                q.push({i, j});
                d[i][j] = 0;
            } else if(grid[i][j] == 'C') {
                endX = i; endY = j;
            }
        }
    }

    while(!q.empty()) {
        Point u = q.front(); q.pop();
        if(u.x == endX && u.y == endY) return to_string(d[u.x][u.y]);

        for(int k=0; k<4; k++) {
            int nx = u.x + dx[k];
            int ny = u.y + dy[k];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if(d[nx][ny] == -1 && grid[nx][ny] != '.') {
                    d[nx][ny] = d[u.x][u.y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    return "Safe";
}

int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<string> grid;

        if (i == 1) { 
            // 样例1
            N = 3; M = 4;
            grid = {"F#..", "##..", ".C.."};
        }
        else if (i == 2) {
            // 样例2 (Safe)
            N = 3; M = 3;
            grid = {"F..", ".#.", "..C"};
        }
        else if (i == 3) {
            // 蛇形迷宫 (测试距离)
            N = 5; M = 5;
            grid = {
                "F####",
                "....#",
                "#####",
                "#....",
                "####C"
            };
        }
        else if (i == 4) {
            // 多源测试 (两个F，看谁先到)
            N = 5; M = 5;
            grid = {
                "F...F",
                ".#.#.",
                ".#C#.", // 左边的F距离2，右边的F距离2，结果应为2
                ".#.#.",
                "....."
            };
        }
        else if (i == 5) {
            // 全是战船 (最短路径 = 曼哈顿距离)
            N = 20; M = 20;
            for(int r=0; r<N; r++) grid.push_back(string(M, '#'));
            grid[0][0] = 'F'; grid[N-1][M-1] = 'C';
        }
        else if (i == 6) {
            // 水域迷宫 (Safe 概率高)
            N = 50; M = 50;
            for(int r=0; r<N; r++) {
                string row = "";
                for(int c=0; c<M; c++) row += (rand()%3 == 0 ? '#' : '.'); 
                grid.push_back(row);
            }
            grid[0][0] = 'F'; grid[N-1][M-1] = 'C';
        }
        else {
            // 大规模随机 (N=1000)
            N = 1000; M = 1000;
            for(int r=0; r<N; r++) {
                string row = "";
                // 70% 概率是船，保证大概率连通
                for(int c=0; c<M; c++) row += (rand()%10 < 7 ? '#' : '.'); 
                grid.push_back(row);
            }
            
            // 放置 F 和 C
            int fx = randRange(0, 100), fy = randRange(0, 100);
            int cx = randRange(N-100, N-1), cy = randRange(M-100, M-1);
            grid[fx][fy] = 'F';
            grid[cx][cy] = 'C';
            
            // Case 9, 10 增加额外火点
            if(i >= 9) {
                for(int k=0; k<20; k++) 
                    grid[randRange(0, N-1)][randRange(0, M-1)] = 'F';
                grid[cx][cy] = 'C'; // 确保 C 不被覆盖
            }
        }

        // 写入输入
        fin << N << " " << M << endl;
        for(const auto& row : grid) fin << row << endl;

        // 写入输出
        fout << solve(N, M, grid) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}