#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vl = V<ll>;
using vb = V<bool>;
using vpii = V<pii>;
using vpll = V<pll>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const ll INF = 2e18;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX_N = 4e3;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int depth[MAX_N][MAX_N];
char grid[MAX_N][MAX_N];
int main() {
fastIO
F0R(i, MAX_N) memset(depth[i], 0, sizeof(depth[i]));
int n, m; cin >> n >> m;
F0R(i, n) {
string s; cin >> s;
F0R(j, m) {
grid[i][j] = s[j];
}
}
auto inrange = [&](pii p) ->bool{
return p.f >= 0 && p.f < n && p.s >= 0 && p.s < m && grid[p.f][p.s] != '.';
};
deque<pii> q; int ans = 0;
q.push_front({0, 0}); depth[0][0] = 1;
while(!q.empty()) {
pii p = q.ft;
q.pop_front();
ckmax(ans, depth[p.f][p.s]);
F0R(i, 4) {
pii np = {p.f + dx[i], p.s + dy[i]};
if (inrange(np) && depth[np.f][np.s] == 0) {
if (grid[p.f][p.s] == grid[np.f][np.s]) {
depth[np.f][np.s] = depth[p.f][p.s];
q.push_front(np);
} else {
depth[np.f][np.s] = depth[p.f][p.s] + 1;
q.pb(np);
}
}
}
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
66240 KB |
Output is correct |
| 2 |
Correct |
20 ms |
64092 KB |
Output is correct |
| 3 |
Correct |
21 ms |
64232 KB |
Output is correct |
| 4 |
Correct |
24 ms |
66392 KB |
Output is correct |
| 5 |
Correct |
20 ms |
65272 KB |
Output is correct |
| 6 |
Correct |
21 ms |
64092 KB |
Output is correct |
| 7 |
Correct |
26 ms |
64348 KB |
Output is correct |
| 8 |
Correct |
20 ms |
64348 KB |
Output is correct |
| 9 |
Correct |
21 ms |
64464 KB |
Output is correct |
| 10 |
Correct |
22 ms |
65108 KB |
Output is correct |
| 11 |
Correct |
21 ms |
64856 KB |
Output is correct |
| 12 |
Correct |
23 ms |
65364 KB |
Output is correct |
| 13 |
Correct |
22 ms |
65236 KB |
Output is correct |
| 14 |
Correct |
21 ms |
65372 KB |
Output is correct |
| 15 |
Correct |
26 ms |
66392 KB |
Output is correct |
| 16 |
Correct |
25 ms |
66388 KB |
Output is correct |
| 17 |
Correct |
23 ms |
66132 KB |
Output is correct |
| 18 |
Correct |
23 ms |
66396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
78680 KB |
Output is correct |
| 2 |
Correct |
39 ms |
70632 KB |
Output is correct |
| 3 |
Correct |
124 ms |
94544 KB |
Output is correct |
| 4 |
Correct |
51 ms |
75180 KB |
Output is correct |
| 5 |
Correct |
78 ms |
84712 KB |
Output is correct |
| 6 |
Correct |
375 ms |
109328 KB |
Output is correct |
| 7 |
Correct |
32 ms |
78684 KB |
Output is correct |
| 8 |
Correct |
26 ms |
78684 KB |
Output is correct |
| 9 |
Correct |
19 ms |
64216 KB |
Output is correct |
| 10 |
Correct |
20 ms |
64092 KB |
Output is correct |
| 11 |
Correct |
24 ms |
78668 KB |
Output is correct |
| 12 |
Correct |
20 ms |
64632 KB |
Output is correct |
| 13 |
Correct |
40 ms |
70492 KB |
Output is correct |
| 14 |
Correct |
46 ms |
68696 KB |
Output is correct |
| 15 |
Correct |
28 ms |
69200 KB |
Output is correct |
| 16 |
Correct |
30 ms |
66384 KB |
Output is correct |
| 17 |
Correct |
102 ms |
75960 KB |
Output is correct |
| 18 |
Correct |
46 ms |
75820 KB |
Output is correct |
| 19 |
Correct |
50 ms |
75088 KB |
Output is correct |
| 20 |
Correct |
49 ms |
74360 KB |
Output is correct |
| 21 |
Correct |
82 ms |
85332 KB |
Output is correct |
| 22 |
Correct |
75 ms |
84680 KB |
Output is correct |
| 23 |
Correct |
124 ms |
81488 KB |
Output is correct |
| 24 |
Correct |
89 ms |
85296 KB |
Output is correct |
| 25 |
Correct |
125 ms |
94484 KB |
Output is correct |
| 26 |
Correct |
174 ms |
139876 KB |
Output is correct |
| 27 |
Correct |
254 ms |
123660 KB |
Output is correct |
| 28 |
Correct |
329 ms |
108972 KB |
Output is correct |
| 29 |
Correct |
345 ms |
104980 KB |
Output is correct |
| 30 |
Correct |
294 ms |
114028 KB |
Output is correct |
| 31 |
Correct |
271 ms |
87008 KB |
Output is correct |
| 32 |
Correct |
234 ms |
113996 KB |
Output is correct |
