解题思路

题目给了一个 n×n 的矩阵，里面有三种数字：

• 1 表示敌人；
• 2 表示没有敌人；
• 0 表示地雷。

我们只要找出 0 在哪一行、哪一列，然后输出它的行号和列号（行号、列号都从 1 开始）。

一个省事的办法是：读矩阵的时候根本不用把整个矩阵存下来，而是“边读边看”——每读到一个数，就检查它是不是 0，是 0 就记下当前的 i（行）和 j（列）。等把矩阵读完，地雷的位置就找到了。

参考代码

// P4443 安放地雷1：在 n*n 的矩阵里找到值为 0 的地雷位置
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;               // 矩阵大小 n*n
    int x = 0, y = 0;       // 记下地雷的行号、列号（从 1 开始）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t;
            cin >> t;       // 读入第 i 行第 j 列的数
            if (t == 0) {   // 0 就是地雷的位置
                x = i;
                y = j;
            }
        }
    }
    cout << x << " " << y << endl;  // 输出行号和列号
    return 0;
}

复杂度分析

设矩阵是 n×n。

• 时间：每个格子都读了一遍并判断一次，时间复杂度是 O(n^2)。
• 空间：只需要几个变量存位置，空间复杂度是 O(1)。