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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <iostream>
#include <vector>
#include <cstring>
using namespace std;
char map[22][22];
int n, colorCheck[26], os[4][2] = { {-1,0}, {0,1}, {1,0},{0,-1} };
vector<pair<pair<int, int>, pair<int, int>>> pcl;
bool visit[22][22];
pair<int, int> q[420];
void getPCL();
void checkSingleRectagle(int, int,int,int);
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
getPCL();
int last = pcl.size() - 1;
for (int i = last; i >=0; i--) {
int si = pcl[i].first.first, sj = pcl[i].first.second, w = pcl[i].second.first, h = pcl[i].second.second;
for (int j = 0; j < i; j++)
if (si >= pcl[j].first.first && sj >= pcl[j].first.second && w <= pcl[j].second.first && h <= pcl[j].second.second) {
pcl.pop_back();
break;
}
}
cout << pcl.size() << endl;
}
void getPCL() {
for (int h = n - 1; h >= 0; h--) {
for (int w = n - 1; w >= 0; w--) {
for (int i = 0; i < n - w; i++) {
for (int j = 0; j < n - h; j++) {
checkSingleRectagle(i, j, i + w, j + h);
memset(colorCheck, 0, sizeof(colorCheck));
}
}
}
}
}
void checkSingleRectagle(int si, int sj, int w, int h) {
for (int i = 0; i < pcl.size(); i++)
if (si >= pcl[i].first.first && sj >= pcl[i].first.second && w <= pcl[i].second.first && h <= pcl[i].second.second)
return;
int count = 0;
for (int i = sj; i <= h; i++) {
for (int j = si; j <= w; j++) {
if (!colorCheck[map[i][j] - 'A'])
count++;
colorCheck[map[i][j] - 'A']++;
if (count > 2)
return;
}
}
if (count != 2)
return;
bool check1 = false;
int check2 = 0;
for (int i = sj; i <= h; i++) {
for (int j = si; j <= w; j++) {
if (!visit[i][j]) {
char c = map[i][j];
int temp = colorCheck[c - 'A'], curIdx = 0, lastIdx = 0;
visit[i][j] = true;
q[lastIdx++] = { i,j };
while (curIdx != lastIdx) {
int ch = q[curIdx].first, cc = q[curIdx].second;
curIdx++;
temp--;
for (int k = 0; k < 4; k++) {
int nh = ch + os[k][0], nc = cc + os[k][1];
if (nh >= sj && nh <= h && nc >= si && nc <= w && !visit[nh][nc] && map[nh][nc] == c) {
q[lastIdx++] = { nh, nc };
visit[nh][nc] = true;
}
}
}
if (temp == 0)
check1 = true;
else
check2++;
}
if (check1 && check2 >= 2)
break;
}
}
memset(visit, 0, sizeof(visit));
if (check1 && check2 >= 2)
pcl.push_back({ {si, sj}, { w, h} });
}
|
