#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e17+1
ll const M = 1e5+10;
ll const N = 100001;
const int mod = 1e9+7;
ll dx[8]={1,0,-1,0,1,-1,-1,1};
ll dy[8]={0,1,0,-1,1,-1,1,-1};
ll gcd(ll a, ll b)
{
return b==0 ? a : gcd(b,a%b);
}
int h,w;
string track[4001];
int depth[4001][4001];
int inside(int x,int y)
{
if(x < h and x >= 0 and y < w and y >= 0 and track[x][y] != '.')return true;
return false;
}
void solve(int t) {
// cout << "Case #" << t << ": ";
cin>>h>>w;
for(int i=0;i<h;i++)
{
cin>>track[i];
}
depth[0][0] = 1;
int ans = 1;
deque<pair<int,int>> q;
q.push_back({0,0});
while(!q.empty())
{
pair<int,int> start = q.front();
q.pop_front();
ans = max(ans, depth[start.first][start.second]);
for(int i=0;i<4;i++)
{
int x = start.first + dx[i];
int y = start.second + dy[i];
if(inside(x,y) and depth[x][y]==0)
{
if(track[x][y] == track[start.first][start.second]) {
depth[x][y] = depth[start.first][start.second];
q.push_front({x,y});
}
else
{
depth[x][y] = depth[start.first][start.second] + 1;
q.push_back({x,y});
}
}
}
}
cout<<ans;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
// int T;
// cin >> T ;
// for(int t = 1; t <= T; t++)
solve(1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
3916 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
7 ms |
3532 KB |
Output is correct |
5 |
Correct |
3 ms |
1996 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
700 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
10 |
Correct |
2 ms |
1620 KB |
Output is correct |
11 |
Correct |
2 ms |
1552 KB |
Output is correct |
12 |
Correct |
4 ms |
2120 KB |
Output is correct |
13 |
Correct |
2 ms |
1996 KB |
Output is correct |
14 |
Correct |
3 ms |
1996 KB |
Output is correct |
15 |
Correct |
9 ms |
3660 KB |
Output is correct |
16 |
Correct |
9 ms |
3788 KB |
Output is correct |
17 |
Correct |
7 ms |
3624 KB |
Output is correct |
18 |
Correct |
7 ms |
3524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15952 KB |
Output is correct |
2 |
Correct |
36 ms |
11908 KB |
Output is correct |
3 |
Correct |
170 ms |
62700 KB |
Output is correct |
4 |
Correct |
53 ms |
28516 KB |
Output is correct |
5 |
Correct |
129 ms |
45424 KB |
Output is correct |
6 |
Correct |
491 ms |
97908 KB |
Output is correct |
7 |
Correct |
10 ms |
16604 KB |
Output is correct |
8 |
Correct |
9 ms |
15948 KB |
Output is correct |
9 |
Correct |
2 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
10 ms |
16332 KB |
Output is correct |
12 |
Correct |
1 ms |
1100 KB |
Output is correct |
13 |
Correct |
31 ms |
11924 KB |
Output is correct |
14 |
Correct |
19 ms |
7808 KB |
Output is correct |
15 |
Correct |
15 ms |
10348 KB |
Output is correct |
16 |
Correct |
15 ms |
4944 KB |
Output is correct |
17 |
Correct |
78 ms |
24132 KB |
Output is correct |
18 |
Correct |
82 ms |
31060 KB |
Output is correct |
19 |
Correct |
54 ms |
28468 KB |
Output is correct |
20 |
Correct |
46 ms |
21852 KB |
Output is correct |
21 |
Correct |
95 ms |
44324 KB |
Output is correct |
22 |
Correct |
126 ms |
45380 KB |
Output is correct |
23 |
Correct |
157 ms |
37736 KB |
Output is correct |
24 |
Correct |
98 ms |
41384 KB |
Output is correct |
25 |
Correct |
295 ms |
83704 KB |
Output is correct |
26 |
Correct |
297 ms |
121604 KB |
Output is correct |
27 |
Correct |
383 ms |
118316 KB |
Output is correct |
28 |
Correct |
504 ms |
97760 KB |
Output is correct |
29 |
Correct |
470 ms |
95268 KB |
Output is correct |
30 |
Correct |
463 ms |
101244 KB |
Output is correct |
31 |
Correct |
370 ms |
64788 KB |
Output is correct |
32 |
Correct |
355 ms |
105636 KB |
Output is correct |