-
Notifications
You must be signed in to change notification settings - Fork 0
/
10026.cpp
123 lines (106 loc) · 2.19 KB
/
10026.cpp
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#define vt vector
#define en '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define ioa insert_or_assign
#define umap unordered_map
#define prq priority_queue
#define pb push_back
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rev(c) (c).rbegin(), (c).rend()
#define mset(ar, val) memset(ar, val, sizeof(ar))
using namespace std;
const int d4r[4] = {-1,0,1,0}; const int d4c[4] = {0,1,0,-1};
const int d8r[8] = {-1,-1,0,1,1,1,0,-1}; const int d8c[8] = {0,1,1,1,0,-1,-1,-1};
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;
int T = 1;
char bd[102][102];
bool vis[102][102];
int N;
int a1,a2;
void bfs1(int r, int c, char ch) {
queue<pii> q;
q.push({r,c});
int nr,nc;
while(!q.empty()) {
pii p = q.front(); q.pop();
r = p.first;
c = p.second;
for(int d=0; d<4; ++d) {
nr = r + d4r[d];
nc = c + d4c[d];
if(1<=nr&&nr<=N && 1<=nc&&nc<=N && !vis[nr][nc] && bd[nr][nc] == ch) {
q.push({nr,nc});
vis[nr][nc] = 1;
}
}
}
}
void bfs2(int r, int c, char ch) {
queue<pii> q;
q.push({r,c});
int nr,nc;
while(!q.empty()) {
pii p = q.front(); q.pop();
r = p.first;
c = p.second;
for(int d=0; d<4; ++d) {
nr = r + d4r[d];
nc = c + d4c[d];
if(1<=nr&&nr<=N && 1<=nc&&nc<=N && !vis[nr][nc]) {
if(ch == 'R' || ch == 'G') {
if(bd[nr][nc] == 'R' || bd[nr][nc] == 'G') {
q.push({nr,nc});
vis[nr][nc] = 1;
}
} else {
if(bd[nr][nc] == ch) {
q.push({nr,nc});
vis[nr][nc] = 1;
}
}
}
}
}
}
void sol() {
scanf("%d", &N);
for(int i=1; i<=N; ++i) {
for(int j=1; j<=N; ++j) {
scanf(" %c", &bd[i][j]);
}
}
for(int i=1; i<=N; ++i) {
for(int j=1; j<=N; ++j) {
if(!vis[i][j]) {
a1++;
vis[i][j] = 1;
bfs1(i,j,bd[i][j]);
}
}
}
mset(vis,0);
for(int i=1; i<=N; ++i) {
for(int j=1; j<=N; ++j) {
if(!vis[i][j]) {
a2++;
vis[i][j] = 1;
bfs2(i,j,bd[i][j]);
}
}
}
printf("%d %d\n", a1, a2);
return;
}
int main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
while(T--) {
sol();
}
return 0;
}