P4704 安放地雷2（入门）

解题思路

第一步：看懂题目。 一个 n×n 的格子地图，格子里有三种数字：1 表示敌人，2 表示空地，0 表示地雷所在的位置。地雷爆炸后，会打中它所在的那一行和那一列上的所有敌人。我们要数一数一共能清除多少个敌人。

第二步：想清楚要做什么。 其实只要做两件事：第一，找到地雷在哪一行哪一列；第二，数出这一行和这一列上一共有几个 1（敌人）。

第三步：想出聪明的做法——边读边统计。 不需要把整张地图都存下来。读地图的时候一边读一边统计：遇到 1，就把这一行的敌人计数加 1，同时把这一列的敌人计数加 1；遇到 0，就记下它的行号和列号。全部读完后，答案就是“地雷所在行的敌人数 + 地雷所在列的敌人数”。

第四步：为什么这样算不会重复？ 地雷的位置是 0，不是 1，所以在统计时它不会给任何一行或一列加计数。地雷所在的那个格子虽然既属于行又属于列，但它不是敌人，不会被重复计算。其他格子要么在行里被算一次，要么在列里被算一次，不可能重叠。

第五步：为什么不存整张地图？ 因为最终只用得到地雷所在行和所在列的敌人数量，其他位置的信息读完就没用了。一边读入一边累计，既省内存又直观，这就是“读数据的同时做预处理”的常用技巧。

第六步：举个例子验证。 用 4×4 的地图，地雷放在第三行第二列。假设第三行的敌人有 2 个，第二列的敌人有 3 个，那么总共能清除 2+3=5 个敌人，和样例输出一致。

第七步：注意边界情况。 如果地雷所在的行或列上没有敌人，那一部分就是 0，答案就是另一部分的数量；如果整行整列都没有敌人，答案就是 0。题目保证地图中 0 只出现一次（只有一颗地雷）。

参考代码

// 安放地雷2：统计地雷所在行、列中敌人(数字1)的总数
#include <iostream>
using namespace std;

int rowCnt[1005], colCnt[1005]; // 每行、每列的敌人数量

int main() {
    int n;
    cin >> n;
    int mineRow = -1, mineCol = -1; // 地雷所在的行号和列号
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cell;
            cin >> cell;
            if (cell == 1) { // 是敌人，所在行、列计数各加一
                rowCnt[i]++;
                colCnt[j]++;
            } else if (cell == 0) { // 0 是地雷位置，记下行号和列号
                mineRow = i;
                mineCol = j;
            }
        }
    }
    cout << rowCnt[mineRow] + colCnt[mineCol] << endl; // 行敌人 + 列敌人
    return 0;
}

复杂度分析

读入 n×n 个格子，每个格子只处理一次，时间复杂度 O(n²)。空间只用了两个长度为 n 的数组来记录每行、每列的敌人数量，O(n)。