题目描述

在一个 $N \times M$ 的网格中，放置了一些水豚 (c 或 w) 和暖炉 (m)，其余位置是空格 (.)。
一个暖炉 (m) 可以使其自身中心 $3 \times 3$ 范围内的所有格子（包括有水豚或空格的格子）变得温暖。
暖呼呼的水豚 (w) 应该处于至少一个暖炉的 $3 \times 3$ 影响范围内。
* 很冷的水豚 (c) 不应该处于任何暖炉的 $3 \times 3$ 影响范围内。

我们称一个网格状态是 合法的，当且仅当同时满足以下两个条件：
1. 所有 w 水豚都在某个暖炉的影响范围内。
2. 所有 c 水豚都不在任何暖炉的影响范围内。

题目中给定的初始网格状态可能 不合法。具体来说，可能存在 最多一只 “不对劲” 的水豚：即一只暖呼呼的水豚 (w)，其周围（包括自身）的 $3 \times 3$ 范围内没有任何可见的暖炉。这暗示可能有一个暖炉被隐藏了（被对话框挡住，对应于输入中的 . 格子）。

你的任务是：找出所有可能的 隐藏暖炉 位置。一个空格子 (r, c) 被认为是可能的隐藏暖炉位置，当且仅当：
1. 初始网格状态是 不合法的。
2. 在格子 (r, c) 放置一个暖炉后，新的网格状态变为 合法的。

输出所有可能的隐藏暖炉位置 (r, c)（1-based 索引），按行优先，同行按列优先的顺序排序。如果没有这样的位置，输出 Too cold!。

样例

输入:
6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.

输出:
2 7
3 5
4 6
4 7

算法 (模拟 + 推理)

$O(N \times M)$

思路分析

1. 理解题意: 核心在于找到一个空格子 .，在这个位置放上一个暖炉 m 后，恰好能使得一个原本不合法的网格状态变为合法。并且，这种不合法性必须源于存在“看起来没有被加热但状态是暖呼呼 (w)”的水豚。

2. 检查初始状态的合法性:

   • 我们需要先判断初始给定的网格状态是否合法。
   • 计算所有 可见 暖炉 m 的影响范围。我们可以用一个二维布尔数组 cov[N+1][M+1] 来标记每个格子 (i, j) 是否被至少一个可见暖炉覆盖。遍历所有 m 的位置 (hr, hc)，将其 $3 \times 3$ 邻域内的所有格子（在边界内的）标记为 cov[i][j] = true。
   • 遍历整个网格，检查是否存在不合法的情况：
     • 情况 A (Unexpectedly Warm): 找到一个 w 水豚位于 (r, c)，但是 cov[r][c] 为 false。这意味着这只水豚暖呼呼的，但周围没有可见的暖炉。我们将这些水豚的位置存入集合 uw (Unexpectedly Warm)。
     • 情况 B (Overheated Cold): 找到一个 c 水豚位于 (r, c)，但是 cov[r][c] 为 true。这意味着这只水豚本应是冷的，却被可见的暖炉加热了。我们将这些水豚的位置存入集合 oc (Overheated Cold)。
   • 判断初始合法性:
     • 如果 uw 和 oc 都为空，说明初始状态就是合法的。根据题目要求（必须从不合法变为合法），不存在满足条件的隐藏暖炉位置。输出 Too cold!。
     • 如果 oc 不为空，说明存在一个 c 水豚被可见暖炉加热了。无论我们在哪个空格子放上隐藏的暖炉，这个 c 水豚仍然会被原来的可见暖炉或者新加的暖炉加热，状态永远无法变为合法。因此，这种情况下也无解。输出 Too cold!。

3. 寻找可能的隐藏暖炉位置:

   • 只有当初始状态 不合法 且 不合法性仅来源于 uw (即 oc 为空，uw 非空) 时，才有可能通过放置一个隐藏暖炉来修复状态。
   • 这个隐藏的暖炉必须能够解释 所有 uw 集合中的水豚为什么是暖的。也就是说，这个隐藏暖炉的位置 (hr, hc) 必须满足：对于 uw 中的 每一个 水豚 (r, c)，(r, c) 都在 (hr, hc) 的 $3 \times 3$ 影响范围内。
   • 反过来看，对于一个 uw 中的水豚 (r, c)，能够使其变暖的潜在暖炉位置集合是其自身的 $3 \times 3$ 邻域（记为 Neighborhood(r, c)）。
   • 因此，隐藏暖炉的 候选 位置必须位于 所有 uw 中水豚的 $3 \times 3$ 邻域的 交集 内。设这个交集为 P。
   • 我们可以通过迭代计算这个交集：
     1. 初始化 P 为第一个 uw 水豚的邻域。
     2. 对于 uw 中剩余的每个水豚 (r, c)，计算 P = P ∩ Neighborhood(r, c)。可以使用 std::set_intersection 来高效计算集合交集。
     3. 如果在任何一步计算交集后 P 变为空集，说明不存在任何一个位置能同时覆盖所有 uw 水豚，无解。输出 Too cold!。（虽然这种情况理论上可能，但代码逻辑中会在最后检查 ans 是否为空）

4. 验证候选位置:
   现在集合 P 中包含了所有能够解释 uw 问题的潜在暖炉位置。但我们还需要对 P 中的每个候选位置 (hr, hc) 进行验证，看放置暖炉后是否会引入新的不合法情况：

   • 条件 1: 候选位置 (hr, hc) 本身必须是空格 .。如果 g[hr-1][hc-1] 不是 .，则不能在这里放置隐藏暖炉。
   • 条件 2: 在 (hr, hc) 放置暖炉后，不能覆盖任何原本是 c 的水豚。遍历 (hr, hc) 的 $3 \times 3$ 邻域内的所有格子 (r, c)，检查 g[r-1][c-1] 是否为 c。如果存在任何一个 c 被新加的暖炉覆盖了，那么 (hr, hc) 就不是一个有效的隐藏暖炉位置。

5. 收集并输出结果:

   • 将所有通过验证的候选位置 (hr, hc) 存入结果列表 ans。
   • 如果 ans 为空，说明没有找到任何有效的隐藏暖炉位置，输出 Too cold!。
   • 如果 ans 不为空，将其按行优先、列优先的顺序排序，然后逐行输出 r 和 c。

时间复杂度

1. 计算初始覆盖范围 cov: 遍历所有可见暖炉（最多 $N \times M$ 个），每个暖炉更新 $3 \times 3 = 9$ 个格子。复杂度 $O(N \times M)$。
2. 识别 uw 和 oc 集合：遍历整个网格一次。复杂度 $O(N \times M)$。
3. 计算邻域交集 P: uw 集合大小最多为 $N \times M$。每个水豚的邻域大小为 9。计算交集的操作。如果使用 std::set，交集操作复杂度与集合大小相关。最坏情况下，P 的大小可能接近 $N \times M$，每次交集操作可能需要 $O(N \times M)$ 或 $O(N \times M \log(NM))$ 时间。总共可能需要 $O((NM)^2)$ 或 $O((NM)^2 \log(NM))$。但是，由于邻域大小固定为 9，交集的大小通常会很快减小。我们可以优化：先计算所有 uw 水豚的邻域（每个 $O(1)$），然后迭代计算交集。如果 uw 的数量为 k，求交集的总复杂度可以更有效地分析。一种更简单的方法是，对每个格子 (i, j)，检查它是否在所有 uw 水豚的邻域内，这需要 $O(NM \times |uw|)$ 时间。代码中使用 std::set_intersection，其复杂度与输入集合大小成线性关系，这里集合大小最多为 9 或 $N \times M$（取决于实现），总复杂度更接近 $O(N \times M \times \min(|uw|, \log(|P|)))$ 或类似界限，通常可以认为是 $O(N \times M)$ 级别的，因为交集大小会快速减小。
4. 验证候选位置 P 中的每个元素：遍历 P 中的每个位置（最多 $N \times M$ 个），对每个位置检查 $3 \times 3$ 邻域（$O(1)$）。复杂度 $O(|P|) \le O(N \times M)$。
5. 排序和输出：$O(|ans| \log |ans|)$，其中 $|ans| \le N \times M$。

整体来看，主要瓶颈在于初始计算和集合操作，时间复杂度接近 O(N × M)。

C++ 代码

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

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题没用到)

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

    int n, m; // 矩阵行数 N, 列数 M
    cin >> n >> m;

    vector<string> g(n); // 存储输入的网格
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }

    // cov[i][j] 标记格子 (i, j) 是否被可见暖炉覆盖 (1-based index)
    vector cov(n + 1, vector<bool>(m + 1, false)); 
    // uw: 存储 Unexpectedly Warm 水豚的位置 {r, c} (1-based)
    set<pair<int, int>> uw; 
    // oc: 存储 Overheated Cold 水豚的位置 {r, c} (1-based)
    set<pair<int, int>> oc; 
    // h: 存储所有可见暖炉的位置 {r, c} (1-based)
    vector<pair<int, int>> h; 

    // 找到所有可见暖炉的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'm') {
                h.push_back({i + 1, j + 1});
            }
        }
    }

    // 计算可见暖炉的覆盖范围
    for (auto [r, c] : h) { // 遍历每个暖炉
        for (int i = r - 1; i <= r + 1; i++) { // 遍历 3x3 邻域
            for (int j = c - 1; j <= c + 1; j++) {
                // 检查边界
                if (i >= 1 && i <= n && j >= 1 && j <= m) {
                    cov[i][j] = true; // 标记为覆盖
                }
            }
        }
    }

    // 检查初始状态的不合法情况
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 情况 A: 'w' 但未被覆盖
            if (g[i - 1][j - 1] == 'w' && !cov[i][j]) {
                uw.emplace(i, j); // 加入 uw 集合
            }
            // 情况 B: 'c' 但被覆盖
            if (g[i - 1][j - 1] == 'c' && cov[i][j]) {
                oc.emplace(i, j); // 加入 oc 集合
            }
        }
    }

    // 判断初始合法性和不可修复情况
    if (uw.empty() && oc.empty()) { // 初始就合法
        cout << "Too cold!\n";
        return 0;
    }

    if (!oc.empty()) { // 存在 'c' 被加热，无法修复
        cout << "Too cold!\n";
        return 0;
    }

    // oc 为空, uw 非空，尝试寻找隐藏暖炉
    // p: 存储所有 uw 水豚邻域的交集，即潜在的隐藏暖炉位置
    set<pair<int, int>> p; 
    bool f = true; // 标记是否是第一个 uw 水豚

    // 计算邻域交集
    for (auto [r, c] : uw) { // 遍历每个 uw 水豚
        set<pair<int, int>> t; // 当前水豚的 3x3 邻域
        for (int i = r - 1; i <= r + 1; i++) {
            for (int j = c - 1; j <= c + 1; j++) {
                if (i >= 1 && i <= n && j >= 1 && j <= m) {
                    t.emplace(i, j); // 加入邻域集合
                }
            }
        }
        if (f) { // 如果是第一个 uw 水豚
            p = t; // 初始化交集 p
            f = false;
        } else { // 如果不是第一个
            set<pair<int, int>> x; // 临时集合用于存储交集结果
            // 计算当前 p 与 t 的交集，结果放入 x
            set_intersection(p.begin(), p.end(), t.begin(), t.end(), inserter(x, x.begin()));
            p = x; // 更新 p 为交集结果
        }
        // 优化：如果交集变为空，提前结束（虽然代码没加，但理论上可以）
        if (p.empty()) {
            break;
        }
    }

    // 验证交集 p 中的候选位置
    vector<pair<int, int>> ans; // 存储最终答案
    for (auto [r, c] : p) { // 遍历每个候选位置
        // 条件 1: 必须是空格 '.'
        if (g[r - 1][c - 1] != '.') {
            continue;
        }
        // 条件 2: 不能加热任何 'c' 水豚
        bool heats_cold = false; // 标记是否会加热 'c'
        for (int i = r - 1; i <= r + 1; i++) { // 检查 3x3 邻域
            for (int j = c - 1; j <= c + 1; j++) {
                if (i >= 1 && i <= n && j >= 1 && j <= m && g[i - 1][j - 1] == 'c') {
                    heats_cold = true; // 发现会加热 'c'
                    break;
                }
            }
            if (heats_cold) {
                break;
            }
        }
        // 如果两个条件都满足
        if (!heats_cold) {
            ans.emplace_back(r, c); // 加入最终答案列表
        }
    }

    // 输出结果
    if (ans.empty()) { // 如果没有找到有效位置
        cout << "Too cold!\n";
    } else {
        // 排序：按行优先，再按列优先
        sort(ans.begin(), ans.end());
        // 输出每个有效位置
        for (auto [r, c] : ans) {
            cout << r << " " << c << "\n";
        }
    }

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