#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cout<<"["#X"]"<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin>>n>>m;
vector brd(n+2, vector(m+2, '.'));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>brd[i][j];
vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
vector dist(n+2, vector(m+2, (int)1e9));
deque<pair<int, int> > q;
q.push_back({1, 1});
dist[1][1] = 1;
while(!q.empty())
{
auto a = q.front();
q.pop_front();
for(int i=0;i<4;i++)
{
int nx = a.first + dx[i], ny = a.second + dy[i];
if(brd[nx][ny] == '.') continue;
int d = 0;
if(brd[nx][ny] != brd[a.first][a.second]) d = 1;
if(dist[nx][ny] > dist[a.first][a.second] + d)
{
dist[nx][ny] = dist[a.first][a.second]+d;
if(d == 0) q.push_front({nx, ny});
if(d == 1) q.push_back({nx, ny});
}
}
}
debug(dist);
int res = 1;
for(auto v : dist)
for(auto u : v)
if(u != 1e9) res = max(res, u);
cout<<res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
464 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
984 KB |
Output is correct |
| 11 |
Correct |
2 ms |
860 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 15 |
Correct |
8 ms |
3004 KB |
Output is correct |
| 16 |
Correct |
10 ms |
2908 KB |
Output is correct |
| 17 |
Correct |
9 ms |
2652 KB |
Output is correct |
| 18 |
Correct |
6 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1124 KB |
Output is correct |
| 2 |
Correct |
47 ms |
15904 KB |
Output is correct |
| 3 |
Correct |
282 ms |
157276 KB |
Output is correct |
| 4 |
Correct |
87 ms |
37208 KB |
Output is correct |
| 5 |
Correct |
198 ms |
88668 KB |
Output is correct |
| 6 |
Correct |
629 ms |
184568 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
860 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1128 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
39 ms |
15900 KB |
Output is correct |
| 14 |
Correct |
22 ms |
9304 KB |
Output is correct |
| 15 |
Correct |
21 ms |
10332 KB |
Output is correct |
| 16 |
Correct |
19 ms |
6744 KB |
Output is correct |
| 17 |
Correct |
129 ms |
40568 KB |
Output is correct |
| 18 |
Correct |
84 ms |
39620 KB |
Output is correct |
| 19 |
Correct |
82 ms |
37216 KB |
Output is correct |
| 20 |
Correct |
62 ms |
34168 KB |
Output is correct |
| 21 |
Correct |
164 ms |
91860 KB |
Output is correct |
| 22 |
Correct |
187 ms |
88860 KB |
Output is correct |
| 23 |
Correct |
214 ms |
76368 KB |
Output is correct |
| 24 |
Correct |
161 ms |
89556 KB |
Output is correct |
| 25 |
Correct |
315 ms |
157296 KB |
Output is correct |
| 26 |
Correct |
349 ms |
218308 KB |
Output is correct |
| 27 |
Correct |
455 ms |
210516 KB |
Output is correct |
| 28 |
Correct |
649 ms |
184640 KB |
Output is correct |
| 29 |
Correct |
669 ms |
181156 KB |
Output is correct |
| 30 |
Correct |
572 ms |
189760 KB |
Output is correct |
| 31 |
Correct |
480 ms |
101924 KB |
Output is correct |
| 32 |
Correct |
428 ms |
187988 KB |
Output is correct |
