#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vpl = vector<pl>;
using vpi = vector<pi>;
using vc = vector<char>;
using vs = vector<string>;
#define forn(i, n) for(int i = 0; i < n; i++)
#define rofn(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, b, a) for(int i = b; i >= a; i--)
#define TRAV(a, x) for(auto& a: x)
#define ABC(c) for(char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<int>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (int)(x).length()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) TRAV(a, x) cout << a << " "
#define print(x) cout << x << endl
#define traverse(x) TRAV(a, x) cout << a.f << " " << a.s << endl
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)
const int MAXN = 4000;
int xDir[4] = {1, -1, 0, 0}, yDir[4] = {0, 0, 1, -1}, dist[MAXN][MAXN], h, w;
char grid[MAXN][MAXN];
bool ok(int i, int j){
if(i >= h || j >= w || i < 0 || j < 0 || grid[i][j] == '.') return false;
return true;
}
void solve(){
cin >> h >> w;
forn(i, h){
forn(j, w){
cin >> grid[i][j];
}
}
int ans = 0;
deque<pi> q;
dist[0][0] = 1;
q.push_front({0, 0});
while(sz(q)){
pi cur = q.front();
q.pop_front();
ans = max(ans, dist[cur.f][cur.s]);
forn(i, 4){
int x = cur.f + xDir[i], y = cur.s + yDir[i];
if(ok(x, y) && dist[x][y] == 0){
if(grid[cur.f][cur.s] == grid[x][y]){
dist[x][y] = dist[cur.f][cur.s];
q.push_front({x, y});
} else {
dist[x][y] = dist[cur.f][cur.s] + 1;
q.push_back({x, y});
}
}
}
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
// int t; cin >> t;
// forn(i, t){
// solve();
// }
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
5324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
716 KB |
Output is correct |
| 4 |
Correct |
11 ms |
5136 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2892 KB |
Output is correct |
| 6 |
Correct |
1 ms |
448 KB |
Output is correct |
| 7 |
Correct |
1 ms |
716 KB |
Output is correct |
| 8 |
Correct |
1 ms |
716 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2508 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2124 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3020 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 15 |
Correct |
15 ms |
5196 KB |
Output is correct |
| 16 |
Correct |
19 ms |
5312 KB |
Output is correct |
| 17 |
Correct |
13 ms |
5196 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
30668 KB |
Output is correct |
| 2 |
Correct |
65 ms |
14912 KB |
Output is correct |
| 3 |
Correct |
418 ms |
62124 KB |
Output is correct |
| 4 |
Correct |
130 ms |
32676 KB |
Output is correct |
| 5 |
Correct |
251 ms |
48652 KB |
Output is correct |
| 6 |
Correct |
877 ms |
96160 KB |
Output is correct |
| 7 |
Correct |
20 ms |
32076 KB |
Output is correct |
| 8 |
Correct |
19 ms |
30668 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
20 ms |
31436 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 13 |
Correct |
64 ms |
14924 KB |
Output is correct |
| 14 |
Correct |
38 ms |
10440 KB |
Output is correct |
| 15 |
Correct |
36 ms |
13004 KB |
Output is correct |
| 16 |
Correct |
29 ms |
5652 KB |
Output is correct |
| 17 |
Correct |
160 ms |
28700 KB |
Output is correct |
| 18 |
Correct |
136 ms |
35520 KB |
Output is correct |
| 19 |
Correct |
121 ms |
32636 KB |
Output is correct |
| 20 |
Correct |
98 ms |
25516 KB |
Output is correct |
| 21 |
Correct |
251 ms |
47300 KB |
Output is correct |
| 22 |
Correct |
253 ms |
48680 KB |
Output is correct |
| 23 |
Correct |
295 ms |
39748 KB |
Output is correct |
| 24 |
Correct |
250 ms |
44700 KB |
Output is correct |
| 25 |
Correct |
612 ms |
82500 KB |
Output is correct |
| 26 |
Correct |
580 ms |
120908 KB |
Output is correct |
| 27 |
Correct |
750 ms |
105332 KB |
Output is correct |
| 28 |
Correct |
855 ms |
92176 KB |
Output is correct |
| 29 |
Correct |
832 ms |
90552 KB |
Output is correct |
| 30 |
Correct |
775 ms |
94792 KB |
Output is correct |
| 31 |
Correct |
625 ms |
63284 KB |
Output is correct |
| 32 |
Correct |
673 ms |
90492 KB |
Output is correct |
