战场地图陷阱门最优放置算法调试：代码仅通过部分测试用例

问题描述 #

给定N×M的战场高度地图，敌军会均匀降落在所有格子，陷阱门可捕获所在格子敌军，且若某格子能通过不升高高度的路径到达陷阱门，该格子敌军也会滑入陷阱门。要求计算捕获所有敌军的最少陷阱门数。

我的实现与问题 #

• 建模方式：采用邻接矩阵，相邻格子间若从前者到后者高度不升高则建边
• 查询逻辑：借助DFS+BFS实现可达顶点查询函数
• 主逻辑：遍历所有未访问顶点，获取其可达顶点集合并标记为已处理，统计集合数量作为结果
• 异常情况：代码仅通过竞赛中的6个测试用例，其余均失败，无法查看测试数据，需排查错误

完整代码 #

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include<algorithm>
#include <vector>
#include<stack>
#include <queue>

#define DEBUG 1

const int MAXD = 100;
const int MAXN = MAXD*MAXD;
using namespace std;
int heights[MAXD][MAXD];
bool adjGraph[MAXN][MAXN];
int w, h;
int n;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int toOne(int x, int y){
    return y*w + x;
}

int oneToX(int o){
    return o % w;
}
int oneToY(int o){
    return o / w;
}

void generateAdj(){
    for (int y1 = 0; y1 < h; ++y1) {
        for (int x1 = 0; x1 < w; ++x1) {
            for (int i = 0; i < 4; ++i) {
                int x2 = x1 + dx[i];
                int y2 = y1 + dy[i];
                if(x2 < 0 || y2 < 0 || x2 >= w || y2 >= h) continue;
                adjGraph[toOne(x1, y1)][toOne(x2, y2)] = heights[y1][x1] >= heights[y2][x2];
            }
        }
    }
}
vector<int> dfs(int u, bool visited[]) {
    visited[u] = true;
    vector<int> reachable = {u};
    for (int v = 0; v < n; v++) {
        if (adjGraph[u][v] && !visited[v]) {
            vector<int> sub_reachable = dfs(v, visited);
            reachable.insert(reachable.end(), sub_reachable.begin(), sub_reachable.end());
        }
    }
    return reachable;
}

vector<int> get_reachable_vertices(int target) {
    bool visited[MAXN] = {false};
    vector<int> reachable = dfs(target, visited);
    queue<int> q;
    for (int u : reachable) {
        visited[u] = true;
        q.push(u);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (adjGraph[v][u] && !visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    vector<int> result;
    for (int u = 0; u < n; u++) {
        if (visited[u]) {
            result.push_back(u);
        }
    }
    return result;
}
bool isElementInVector(std::vector<int>& vec, int elem) {
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == elem) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> h >> w;
    n = w*h;
    if(n == 1){
        cout << 1;
        exit(0);
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> heights[i][j];
        }
    }
    #ifdef DEBUG
    cout << "w:" << w << ", h:" << h << "\n";
    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            int o = toOne(x, y);
            if(oneToX(o) != x || oneToY(o) != y) {
                cout << "ABOBA" << x <<", " << y;
            }
        }
    }
    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            cout << heights[y][x] << " ";
        }
        cout << "\n";
    }
    #endif
    generateAdj();

    #ifdef DEBUG
    for (int y1 = 0; y1 < h; ++y1) {
        for (int x1 = 0; x1 < w; ++x1) {
            for (int y2 = 0; y2 < h; ++y2) {
                for (int x2 = 0; x2 < w; ++x2) {
                    if(adjGraph[toOne(x1, y1)][toOne(x2, y2)]) {
                        cout << x1 << "," << y1 << " -> " << x2 << "," << y2 << " " << "\n";
                    }
                }
            }
        }
    }
    #endif
    vector<int> reachable;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if(!isElementInVector(reachable, i)) {
            count++;
            vector<int> reachable2 = get_reachable_vertices(i);
            // Output the result
#ifdef DEBUG
            cout << "aaaa(" << oneToX(i) << ", " << oneToY(i) << "), ";
            cout << "Vertices that can reach all other vertices: ";
            for (int j : reachable2) {
                if(!isElementInVector(reachable, j)) {
                    cout << "(" << oneToX(j) << ", " << oneToY(j) << "), ";
                }
            }
            cout << endl;
#endif
            reachable.insert(reachable.end(), reachable2.begin(), reachable2.end());
        }

    }
    cout << count;
    return 0;
}

核心错误分析 #

1. 可达性逻辑完全颠倒 #

题目要求的是某格子能通过不升高路径到达陷阱门，即陷阱门是终点，格子是起点，需要找所有能到达陷阱门的节点。但你的get_reachable_vertices函数逻辑完全相反：

• 先DFS从target出发，找出target能到达的节点（即陷阱门能走到的格子）
• 再反向BFS找能到达这些节点的节点，完全偏离了需求。正确逻辑应该是：找所有**能到达target**的节点，而不是target能到达的节点。

2. 邻接矩阵边方向适配错误 #

你建边的逻辑是adjGraph[u][v] = heights[u对应格子] >= heights[v对应格子]，表示从u到v可以走（不升高）。但题目中需要的是：对于陷阱门t，所有存在路径到t的节点都能被捕获。因此需要构建反向图（即v到u有边当且仅当原图u到v有边），或者在查询时找所有能到达t的节点。

3. 低效的已访问检查 #

isElementInVector函数遍历vector检查元素是否存在，时间复杂度O(k)（k为已处理节点数），当N×M较大时（比如100×100=10000节点），会导致严重超时，这也是部分测试用例失败的原因之一。应该用全局bool visited[MAXN]数组标记已处理节点，实现O(1)查询。

4. 模型理解偏差 #

问题本质是求原图强连通分量缩点后DAG中出度为0的节点数量：

• 同一个强连通分量中的节点相互可达，在其中任意点放陷阱即可覆盖整个分量
• DAG中出度为0的分量无法到达其他分量，必须每个分量都放置一个陷阱
  你的代码未处理强连通分量，直接遍历节点的逻辑会重复统计或漏统计。

修正方案 #

1. 修正可达性查询逻辑 #

构建反向图，从陷阱门出发遍历反向图，得到所有能到达该陷阱门的节点：

bool reverseAdj[MAXN][MAXN];
void generateReverseAdj() {
    memset(reverseAdj, 0, sizeof(reverseAdj));
    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            if (adjGraph[u][v]) {
                reverseAdj[v][u] = true;
            }
        }
    }
}

vector<int> get_can_reach_target(int target) {
    bool visited[MAXN] = {false};
    queue<int> q;
    q.push(target);
    visited[target] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; ++v) {
            if (reverseAdj[u][v] && !visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    vector<int> res;
    for (int i = 0; i < n; ++i) {
        if (visited[i]) res.push_back(i);
    }
    return res;
}

2. 替换高效的已访问标记 #

用数组替代vector做已处理标记：

bool processed[MAXN] = {false};
int count = 0;
for (int i = 0; i < n; ++i) {
    if (!processed[i]) {
        count++;
        vector<int> covered = get_can_reach_target(i);
        for (int u : covered) {
            processed[u] = true;
        }
    }
}
cout << count << endl;

3. 优化内存占用 #

邻接矩阵在MAXN=10000时会占用约100MB内存，超出部分竞赛题限制，建议改用邻接表（vector<int> adj[MAXN]）存储图结构。

内容的提问来源于stack exchange，提问作者Vasiliy Platon