Nordic Camping 题解

一、问题分析

给定一个 $N \times M$ 的网格，其中 '.' 表示可用区域，'#' 表示障碍物。需要回答 $Q$ 个查询，每个查询要求找出覆盖指定位置 $(x,y)$ 的最大全可用正方形帐篷的面积。

二、算法思路与代码实现

1. 二维前缀和预处理

目的：快速计算任意矩形区域内障碍物的数量，为后续的二分查找提供 $O(1)$ 查询。

const int N = 2005;
int n, m, q;
char g[N][N];
int sum[N][N], len[N][N];

cin >> n >> m;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> g[i][j];
        // 计算二维前缀和：上方矩形 + 左方矩形 - 重复部分 + 当前格子
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        if (g[i][j] == '#') sum[i][j]++;
    }
}

原理：利用容斥原理，sum[i][j] 表示从 $(1,1)$ 到 $(i,j)$ 矩形区域内的障碍物总数。

2. 二分查找确定初始最大边长

目的：对于每个位置 $(i,j)$，找出以它为左上角的最大可用正方形边长。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (g[i][j] == '#') {
            len[i][j] = 0;  // 障碍物位置无法作为起点
            continue;
        }
        // 二分查找：l=0, r=最大可能边长
        int l = 0, r = min(n-i+1, m-j+1);
        while (l <= r) {
            int mid = (l + r) / 2;
            int x = i+mid-1, y = j+mid-1;  // 正方形右下角坐标
            
            // 计算正方形区域内障碍物数量
            int cnt = sum[x][y] - sum[x][j-1] - sum[i-1][y] + sum[i-1][j-1];
            if (cnt == 0) {
                l = mid + 1;  // 无障碍物，尝试更大的边长
            } else {
                r = mid - 1;  // 有障碍物，缩小边长
            }
        }
        len[i][j] = r;  // 记录最大有效边长
    }
}

时间复杂度：$O(NM \log(\min(N,M)))$

3. 单调队列优化

目的：将问题从"以该点为左上角"转化为"包含该点"，确保每个位置的值表示包含该位置的最大正方形边长。

行方向优化

struct Node {
    int val, pos;  // 值, 有效范围终点
};

for (int i = 1; i <= n; i++) {
    deque<Node> dq;
    for (int j = 1; j <= m; j++) {
        // 移除超出有效范围的元素
        while (!dq.empty() && dq.front().pos < j) dq.pop_front();
        
        // 维护单调递减性
        while (!dq.empty() && dq.back().val < len[i][j]) dq.pop_back();
        
        // 加入当前元素，记录其有效范围
        dq.push_back({len[i][j], j + len[i][j] - 1});
        
        // 当前位置的最大边长为队列头部元素
        len[i][j] = dq.front().val;
    }
}

列方向优化

for (int j = 1; j <= m; j++) {
    deque<Node> dq;
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front().pos < i) dq.pop_front();
        while (!dq.empty() && dq.back().val < len[i][j]) dq.pop_back();
        dq.push_back({len[i][j], i + len[i][j] - 1});
        len[i][j] = dq.front().val;
    }
}

关键思想：通过两次单调队列处理，每个位置 len[i][j] 现在表示包含点 $(i,j)$ 的最大正方形边长。

4. 面积计算与查询处理

// 将边长转换为面积
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        len[i][j] = len[i][j] * len[i][j];
    }
}

// 处理查询
cin >> q;
while (q--) {
    int x, y;
    cin >> x >> y;
    cout << len[x][y] << "\n";  // O(1) 时间回答
}

三、复杂度分析

• 时间复杂度：
  • 预处理：$O(NM \log(\min(N,M)))$
  • 单调队列优化：$O(NM)$
  • 查询处理：$O(Q)$
• 空间复杂度：$O(NM)$

四、算法优势

$1$. 高效预处理：二维前缀和实现 $O(1)$ 区域查询

$2$. 单调队列优化：巧妙地将问题转化为更易处理的形式

$3$. 二分查找：快速确定最大可能边长

$4$. 查询高效：预处理后每个查询只需 $O(1)$ 时间

该算法能够高效处理题目约束下的所有数据范围，是解决此类二维区间最大正方形问题的经典方法。