CF203B

_RainCappuccino_ · 2023-04-30 12:02:24 · 题解

题意

有一个 n\times n 大小的矩阵，初始均为 0，现在，给出 m 个操作，使 (x,y) 变为 1，问执行到第几个操作时存在一个 3\times3 的全 1 子矩阵。

思路

最容易想到的就是暴力枚举，每执行一次操作就在矩阵中判断是否存在题目要求的子矩阵，但是这样时间复杂度为 O(mn^2) 一定会超时。

所以，我们不妨从当前操作的格子出发，判断包含它的 3 \times 3 子矩阵是否为全 1 子矩阵即可。如果是，则直接输出当前操作编号，如果执行完 m 次操作后仍然不存在符合要求的子矩阵，则直接输出 -1。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3000 + 5;
int n, m, a[MAXN][MAXN], x, y;//a数组储存矩阵
int dx[10] = {1, 1, 1, -1, -1, -1, 0, 0, 0};//3*3矩阵x坐标变化
int dy[10] = {0, -1, 1, 0, -1, 1, 0, -1, 1};//3*3矩阵y坐标变化
bool check(int x, int y) {//判断条件
    for (int i = 0; i < 9; i++) {
        if (!a[x + dx[i]][y + dy[i]]) {
            return false;
        }
    }
    return true;
}
signed main() {
    scanf("%lld%lld", &n, &m);

    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &x, &y);
        a[x][y] = 1;//标记
        for (int j = 0; j < 9; j++) {//依次讨论包含（x,y）的矩阵中心点
            if (check(x + dx[j], y + dy[j])){//判断
                printf("%lld", i);//输出编号
                return 0;
            }
        }
    }
    printf("-1");
    return 0;
}