新大陆
首先预处理，设第 $i$ 行第 $j$ 列的元素为$a_{ij}$ ，定义数组 $cnt_{ij}$ 统计第 $i$ 行以 $a_{ij}$ 开头且后面元素均等于 $a_{ij}$ 的子数组的最大长度。
一个子矩阵有 $h\times w$ 和 $w\times h$ 两种形式，以 $h\times w$ 为例：
从上至下，从左到右遍历 $a_{ij}$ ，定义数组 $b_{ij}$ 统计以 $a_{ij}$ 为左下角且长大于等于 $h$ 的子矩阵的最大行数，具体计算方法为：若 $cnt[i][j]\ge h$ ，则 $b[i][j]=1$ ，若又有 $a[i][j]=a[i-1][j]$ ，则 $b[i][j]+=b[i-1][j]$。当 $b[i][j]=w$ 时说明存在满足题意的子矩阵。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include "iostream"
#include "vector"
#include "string"
#include "utility"
#include "queue"
#include "set"
#include "map"
#include "unordered_map"
#include "algorithm"
#include "cstring"
#include "stack"
#include "cmath"
#include "numeric"
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
int n, m, h, w;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin >> n >> m;
vector<vector<ll>> a(n + 1, vector<ll>(m + 1, -1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
cin >> h >> w;
vector<vector<int>> cnt(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--) {
if (j == m || a[i][j] != a[i][j + 1])
cnt[i][j] = 1;
else
cnt[i][j] = cnt[i][j + 1] + 1;
}
bool ok = false;
vector<vector<int>> b(n + 1, vector<int>(m + 1, 0));
vector<vector<int>> c(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (cnt[i][j] >= h) {
if (a[i][j] == a[i - 1][j])
b[i][j] = b[i - 1][j] + 1;
else
b[i][j] = 1;
}
if (b[i][j] == w)
ok = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (cnt[i][j] >= w) {
if (a[i][j] == a[i - 1][j])
c[i][j] = c[i - 1][j] + 1;
else
c[i][j] = 1;
}
if (c[i][j] == h)
ok = true;
}
if (ok) cout << "YES";
else cout << "NO";
return 0;
}
|