#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 4e3 + 2;
int c[N][N], n, m, iden;
short a[N][N];
bool Can(int x, int y) {return 0 <= x && x < n && 0 <= y && y < m && c[x][y] == -1;}
void Dfs(int ii, int jj) {
stack<pair<int, int>> st;
st.push({ii, jj});
while (!st.empty()) {
int i = st.top().first;
int j = st.top().second;
st.pop();
c[i][j] = iden;
if (Can(i - 1, j) && a[i - 1][j] == a[i][j]) st.push({i - 1, j});
if (Can(i, j - 1) && a[i][j - 1] == a[i][j]) st.push({i, j - 1});
if (Can(i + 1, j) && a[i + 1][j] == a[i][j]) st.push({i + 1, j});
if (Can(i, j + 1) && a[i][j + 1] == a[i][j]) st.push({i, j + 1});
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++) {
c[i][j] = -1;
if (s[j] == 'F') a[i][j] = 1;
if (s[j] == 'R') a[i][j] = 2;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (c[i][j] == -1 && a[i][j] > 0) {
Dfs(i, j);
iden += 1;
}
}
}
vector<set<int>> g(iden);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (c[i][j] == -1) continue;
if (i < n - 1 && c[i + 1][j] != c[i][j] && c[i + 1][j] != -1) {
g[c[i][j]].insert(c[i + 1][j]);
g[c[i + 1][j]].insert(c[i][j]);
}
if (j < m - 1 && c[i][j + 1] != c[i][j] && c[i][j + 1] != -1) {
g[c[i][j]].insert(c[i][j + 1]);
g[c[i][j + 1]].insert(c[i][j]);
}
}
}
vector<int> dist(iden, 1e9);
queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int s = q.front(); q.pop();
for (int u : g[s]) {
if (dist[u] > dist[s] + 1) {
dist[u] = dist[s] + 1;
q.push(u);
}
}
}
int ans = 0;
for (int i = 0; i < iden; i++) {
smax(ans, dist[i] + 1);
}
cout << ans << en;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
12492 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
15 ms |
5596 KB |
Output is correct |
5 |
Correct |
6 ms |
4308 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
5 ms |
3924 KB |
Output is correct |
11 |
Correct |
4 ms |
2260 KB |
Output is correct |
12 |
Correct |
13 ms |
5608 KB |
Output is correct |
13 |
Correct |
5 ms |
4308 KB |
Output is correct |
14 |
Correct |
5 ms |
4308 KB |
Output is correct |
15 |
Correct |
29 ms |
12116 KB |
Output is correct |
16 |
Correct |
41 ms |
12480 KB |
Output is correct |
17 |
Correct |
24 ms |
11500 KB |
Output is correct |
18 |
Correct |
12 ms |
5588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31916 KB |
Output is correct |
2 |
Correct |
118 ms |
49992 KB |
Output is correct |
3 |
Correct |
569 ms |
313640 KB |
Output is correct |
4 |
Correct |
164 ms |
76120 KB |
Output is correct |
5 |
Correct |
913 ms |
717088 KB |
Output is correct |
6 |
Correct |
1341 ms |
175784 KB |
Output is correct |
7 |
Correct |
16 ms |
33240 KB |
Output is correct |
8 |
Correct |
15 ms |
31956 KB |
Output is correct |
9 |
Correct |
4 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
14 ms |
32304 KB |
Output is correct |
12 |
Correct |
4 ms |
3284 KB |
Output is correct |
13 |
Correct |
116 ms |
50032 KB |
Output is correct |
14 |
Correct |
81 ms |
30760 KB |
Output is correct |
15 |
Correct |
68 ms |
34852 KB |
Output is correct |
16 |
Correct |
55 ms |
21832 KB |
Output is correct |
17 |
Correct |
286 ms |
119560 KB |
Output is correct |
18 |
Correct |
274 ms |
119448 KB |
Output is correct |
19 |
Correct |
159 ms |
76092 KB |
Output is correct |
20 |
Correct |
143 ms |
82904 KB |
Output is correct |
21 |
Correct |
339 ms |
203928 KB |
Output is correct |
22 |
Correct |
951 ms |
717212 KB |
Output is correct |
23 |
Correct |
563 ms |
217104 KB |
Output is correct |
24 |
Correct |
429 ms |
283568 KB |
Output is correct |
25 |
Correct |
1128 ms |
424172 KB |
Output is correct |
26 |
Correct |
546 ms |
194864 KB |
Output is correct |
27 |
Correct |
735 ms |
157352 KB |
Output is correct |
28 |
Correct |
1302 ms |
175760 KB |
Output is correct |
29 |
Correct |
1187 ms |
142276 KB |
Output is correct |
30 |
Correct |
1022 ms |
126536 KB |
Output is correct |
31 |
Correct |
1609 ms |
361040 KB |
Output is correct |
32 |
Correct |
673 ms |
139504 KB |
Output is correct |