题目描述

在一个 $M \times N$ 的网格地图上进行夺宝大赛。地图包含三种格子：
1: 可通行的方格
0: 障碍物，不可通行
* 2: 大本营宝藏位置（地图中只有一个大本营）

有 $K$ 支参赛队伍，每支队伍 $i$ ($1 \le i \le K$) 的初始位置为 $(x_i, y_i)$（注意，输入格式是先列后行，但约定是先 x 后 y，这里 x 代表列，y 代表行。而通常我们习惯用 (行, 列)。需要注意坐标系转换）。

游戏规则：
所有队伍同时从各自的初始位置出发，向大本营移动。
从一个格子移动到相邻（有公共边）的无障碍格子需要 1 个单位时间。
所有队伍都以最快速度（最短路径）冲向大本营。
如果有多支队伍在同一时间到达大本营，它们会发生火拼，所有参与火拼的队伍都无法获胜。
* 只有最早到达大本营且没有发生火拼的队伍才能获胜。

需要确定哪支队伍获胜，并输出其编号和到达时间。如果没有队伍能获胜，输出 No winner.。

地图坐标系：左上角为 (1, 1)，右下角为 (n, m) (列数 n, 行数 m)。

样例 1

输入:
5 7  (m=5, n=7)
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1  (大本营在 (3, 4))
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7      (k=7)
1 5    (队伍1: 列1, 行5) -> (5, 1)
7 1    (队伍2: 列7, 行1) -> (1, 7)
1 1    (队伍3: 列1, 行1) -> (1, 1)
5 5    (队伍4: 列5, 行5) -> (5, 5)
3 1    (队伍5: 列3, 行1) -> (1, 3)
3 5    (队伍6: 列3, 行5) -> (5, 3)
1 4    (队伍7: 列1, 行4) -> (4, 1)

输出:
7 6

样例解释：
队伍到达大本营 (3, 4) 的最短时间：
队伍 1 (5, 1) -> (3, 4): 时间 7
队伍 2 (1, 7) -> (3, 4): 无法到达 (被障碍物阻挡)
队伍 3 (1, 1) -> (3, 4): 时间 5
队伍 4 (5, 5) -> (3, 4): 时间 3
队伍 5 (1, 3) -> (3, 4): 时间 3
队伍 6 (5, 3) -> (3, 4): 时间 5
* 队伍 7 (4, 1) -> (3, 4): 时间 6

到达时间统计：
时间 3: 队伍 4, 队伍 5 (发生火拼)
时间 5: 队伍 3, 队伍 6 (发生火拼)
时间 6: 队伍 7
时间 7: 队伍 1

最早到达且未火拼的队伍是队伍 7，时间为 6。

样例 2

输入:
5 7
... (地图同上) ...
7
7 5   (队伍1: 5, 7)
1 3   (队伍2: 3, 1)
7 1   (队伍3: 1, 7)
1 1   (队伍4: 1, 1)
5 5   (队伍5: 5, 5)
3 1   (队伍6: 1, 3)
3 5   (队伍7: 5, 3)

输出:
No winner.

解释：
到达时间：
队伍 1 (5, 7): 5
队伍 2 (3, 1): 3
队伍 3 (1, 7): 无法到达
队伍 4 (1, 1): 5
队伍 5 (5, 5): 3
队伍 6 (1, 3): 3
队伍 7 (5, 3): 5
到达时间统计：
时间 3: 队伍 2, 5, 6 (火拼)
* 时间 5: 队伍 1, 4, 7 (火拼)
没有队伍能单独最早到达。

算法 (广度优先搜索 BFS)

$O(N \times M + K)$

思路分析

1. 核心问题: 我们需要计算每支队伍到达大本营的最短时间。由于移动时间都是 1，这是典型的无权图最短路径问题，可以使用广度优先搜索 (BFS) 来解决。

2. BFS 起点: 通常 BFS 是从起点开始搜索到终点。但这里我们有多个起点（各队伍的初始位置）和一个共同的终点（大本营）。为了避免对每支队伍都运行一次 BFS，我们可以反向思考：从 大本营 开始运行一次 BFS，计算出大本营到地图上所有可达格子的最短时间。

3. 反向 BFS:

   • 将大本营 (sx, sy) 作为 BFS 的源点，其距离（时间）设为 0。
   • 使用一个队列 que 来存储待访问的格子。
   • 使用一个二维数组 d[n+1][m+1] 来存储从大本营到达每个格子 (i, j) 的最短时间，初始化所有值为 -1（表示未到达或不可达）。
   • 将大本营 (sx, sy) 加入队列，并设置 d[sx][sy] = 0。
   • BFS 过程:
     • 当队列不为空时：
       • 取出队首格子 (x, y)。
       • 遍历其四个相邻格子 (nx, ny)（上、下、左、右）。
       • 对于每个相邻格子 (nx, ny)，检查：
         • 是否在地图边界内 (1 <= nx <= n, 1 <= ny <= m)？
         • 是否是可通行的格子 (g[nx][ny] == 1)？ （注意：大本营 g[sx][sy]==2 也是可达的起点，但在 BFS 扩展时，我们只关心能从 (x,y) 走到 (nx,ny)，所以只检查 g[nx][ny]==1 即可。或者更准确地说，检查 g[nx][ny] != 0 且 (nx, ny) 未被访问过。）
         • 是否尚未计算过距离 (d[nx][ny] == -1)？
       • 如果所有条件都满足：
         • 将 (nx, ny) 加入队列。
         • 设置其距离：d[nx][ny] = d[x][y] + 1。
   • BFS 结束后，d[i][j] 就存储了从大本营出发到达格子 (i, j) 的最短时间。反过来看，这也等于从格子 (i, j) 出发到达大本营的最短时间。

4. 处理队伍信息:

   • 对于每支队伍 i，其初始位置为 (xi, yi) (注意坐标转换)。我们需要查询 d[xi][yi] 来获取其到达大本营的最短时间 ti = d[xi][yi]。
   • 如果 ti == -1，表示该队伍无法到达大本营。

5. 确定获胜者:

   • 我们需要找到所有队伍中，到达时间 ti 最小的值 min_time。
   • 然后，统计有多少支队伍的到达时间恰好是 min_time。
     • 可以使用一个 unordered_map<int, int> cnt 或者 map<int, int> cnt 来统计每个到达时间出现的次数。遍历所有队伍 i=1..k，如果 d[xi][yi] != -1，则 cnt[d[xi][yi]]++。
   • 再次遍历所有队伍 i=1..k：
     • 获取其到达时间 ti = d[xi][yi]。
     • 如果 ti == -1，跳过。
     • 如果 cnt[ti] > 1，表示这个时间有多支队伍到达，发生火拼，跳过。
     • 如果 cnt[ti] == 1，表示这支队伍在该时间唯一到达。
     • 在所有唯一到达的队伍中，找到时间 ti 最小的那支队伍。维护一个 min_time_unique 和对应的获胜队伍编号 winner_id。
   • 如果最终 winner_id 仍然是初始值（例如 -1），则表示没有队伍能获胜，输出 No winner.。
   • 否则，输出 winner_id 和 min_time_unique。

6. 代码实现细节:

   • 注意输入是 $m \times n$，但通常我们习惯用 n 表示行数，m 表示列数。代码中变量 n, m 与题目描述的 $m, n$ 可能相反。仔细看代码：cin >> n >> m; vector<vector<int>> g(n + 1, vector<int>(m + 1)); 这表明代码中 n 对应题目的 $m$ (行数)，m 对应题目的 $n$ (列数)。坐标系是 1-based。
   • 大本营坐标 (sx, sy) 是在读入地图时记录的。
   • 队伍坐标读入时是 x y (列，行)，代码存储时使用了 pair<int, int> {y, x}，即将行放在前面，符合二维数组的习惯。des[i] 存储第 i 队的坐标 (行, 列)。
   • BFS 使用 deque 实现，存储 array<int, 2> 表示坐标。
   • cnt 使用 unordered_map 统计时间频率。
   • 最后遍历队伍，找到时间最小且 cnt 为 1 的队伍。

时间复杂度

• 读取地图和队伍信息: O(N * M + K)。
• 反向 BFS: 每个格子最多访问一次，每个边最多访问一次。复杂度为 O(N * M)。
• 统计时间频率: O(K)。
• 寻找获胜者: O(K)。
• 总时间复杂度: O(N * M + K)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

// 四个方向的坐标偏移量 (下, 上, 右, 左)
constexpr int dx[] = {1, -1, 0, 0}; 
constexpr int dy[] = {0, 0, 1, -1};

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; // 读入地图的行数 n (对应题目 m), 列数 m (对应题目 n)
    cin >> n >> m;

    // g[i][j]: 地图状态 (0:障碍, 1:通路, 2:大本营)
    vector<vector<int>> g(n + 1, vector<int>(m + 1)); 
    // d[i][j]: 从大本营到格子 (i, j) 的最短时间，-1 表示不可达
    vector<vector<int>> d(n + 1, vector<int>(m + 1, -1)); 
    int sx, sy; // 大本营的坐标 (行, 列)

    // 读入地图信息，并找到大本营坐标
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 2) {
                sx = i; // 记录大本营行坐标
                sy = j; // 记录大本营列坐标
            }
        }
    }

    int q; // 队伍数量 k
    cin >> q;
    // des[i] 存储第 i 支队伍的初始坐标 (行, 列)
    vector<pair<int, int>> des(q + 1); 
    for (int i = 1; i <= q; i++) {
        int x, y; // 输入坐标 (列 x, 行 y)
        cin >> x >> y;
        des[i] = {y, x}; // 存储为 (行 y, 列 x)
    }

    // --- 反向 BFS ---
    deque<array<int, 2>> que; // BFS 队列，存储 {行, 列}
    que.push_back({sx, sy}); // 将大本营加入队列
    d[sx][sy] = 0; // 大本营到自身的距离为 0

    while (!que.empty()) {
        auto [x, y] = que.front(); // 取出队首格子 (行 x, 列 y)
        que.pop_front();

        // 遍历四个相邻方向
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k]; // 计算相邻格子的行坐标
            int ny = y + dy[k]; // 计算相邻格子的列坐标

            // 检查边界
            if (nx < 1 || ny < 1 || nx > n || ny > m) {
                continue;
            }
            // 检查是否是障碍物 (g==0) 或已被访问 (d!=-1)
            // 注意: g[nx][ny] == 0 表示障碍物。 g[nx][ny] == 1 或 2 都可以通行。
            // 但因为大本营是起点，不会再被加入队列，所以这里只判断 !g[nx][ny] (即 g[nx][ny]==0) 就够了
            // 或者更严谨地判断 g[nx][ny] != 0 且 d[nx][ny] == -1
            if (!g[nx][ny] || d[nx][ny] != -1) { 
                continue;
            }

            // 将合法且未访问的邻居加入队列
            que.push_back({nx, ny});
            // 更新距离
            d[nx][ny] = d[x][y] + 1;
        }
    }

    // --- 统计和确定获胜者 ---
    // cnt[time] 存储到达时间为 time 的队伍数量
    unordered_map<int, int> cnt; 
    for (int i = 1; i <= q; i++) {
        auto [x, y] = des[i]; // 获取第 i 队坐标 (行, 列)
        if (d[x][y] != -1) { // 如果可以到达大本营
            cnt[d[x][y]]++; // 对应时间的计数加 1
        }
    }

    int mn = 1e9; // 记录当前找到的唯一最早到达时间，初始化为无穷大
    int ans = -1; // 记录获胜队伍的编号，初始化为 -1

    // 再次遍历所有队伍
    for (int i = 1; i <= q; i++) {
        auto [x, y] = des[i]; // 获取第 i 队坐标
        // 跳过无法到达或发生火拼的队伍
        if (d[x][y] == -1 || cnt[d[x][y]] > 1) { 
            continue;
        }
        // 如果这支队伍是唯一到达，并且其时间比当前记录的最小唯一时间 mn 更小
        if (d[x][y] < mn) {
            mn = d[x][y]; // 更新最小唯一时间
            ans = i; // 更新获胜队伍编号
        }
    }

    // 输出结果
    if (ans == -1) { // 如果没有找到获胜者
        cout << "No winner.\n";
    } else { // 否则输出获胜者编号和时间
        cout << ans << " " << mn << "\n";
    }

    return 0; // 程序正常结束
}