#include <bits/stdc++.h>
#define N 4003
#define NN 16000002
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, ans, cnt, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dist[N][N];
char mat[N][N], T;
vector<int> grafo[NN];
int bfs01()
{
deque < pii > bfs;
bfs.push_back({1, 1});
memset(dist, 0x3f3f3f3f, sizeof dist);
dist[1][1] = 1;
while(!bfs.empty())
{
int x = bfs.front().f, y = bfs.front().s;
bfs.pop_front();
ans = max(ans, dist[x][y]);
for(int p = 0; p < 4; p++)
{
int a = x + dx[p], b = y + dy[p];
if(!a or !b or a > n or b > m or mat[a][b] == '.') continue;
int custo = (mat[a][b] == mat[x][y] ? 0 : 1);
if(dist[a][b] > dist[x][y] + custo)
{
dist[a][b] = dist[x][y] + custo;
if(!custo) bfs.push_front({a, b});
else bfs.push_back({a, b});
}
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin>>mat[i][j];
cout<<bfs01()<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
465 ms |
440816 KB |
Output is correct |
| 2 |
Correct |
418 ms |
440816 KB |
Output is correct |
| 3 |
Correct |
387 ms |
440816 KB |
Output is correct |
| 4 |
Correct |
395 ms |
441216 KB |
Output is correct |
| 5 |
Correct |
430 ms |
441216 KB |
Output is correct |
| 6 |
Correct |
452 ms |
441216 KB |
Output is correct |
| 7 |
Correct |
391 ms |
441216 KB |
Output is correct |
| 8 |
Correct |
366 ms |
441216 KB |
Output is correct |
| 9 |
Correct |
389 ms |
441216 KB |
Output is correct |
| 10 |
Correct |
383 ms |
441216 KB |
Output is correct |
| 11 |
Correct |
371 ms |
441216 KB |
Output is correct |
| 12 |
Correct |
388 ms |
441216 KB |
Output is correct |
| 13 |
Correct |
380 ms |
441216 KB |
Output is correct |
| 14 |
Correct |
384 ms |
441216 KB |
Output is correct |
| 15 |
Correct |
440 ms |
441216 KB |
Output is correct |
| 16 |
Correct |
451 ms |
441216 KB |
Output is correct |
| 17 |
Correct |
405 ms |
441216 KB |
Output is correct |
| 18 |
Correct |
449 ms |
441216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
426 ms |
453996 KB |
Output is correct |
| 2 |
Correct |
439 ms |
453996 KB |
Output is correct |
| 3 |
Correct |
768 ms |
454784 KB |
Output is correct |
| 4 |
Correct |
501 ms |
454784 KB |
Output is correct |
| 5 |
Correct |
633 ms |
454784 KB |
Output is correct |
| 6 |
Correct |
1310 ms |
468072 KB |
Output is correct |
| 7 |
Correct |
393 ms |
468072 KB |
Output is correct |
| 8 |
Correct |
396 ms |
468072 KB |
Output is correct |
| 9 |
Correct |
392 ms |
468072 KB |
Output is correct |
| 10 |
Correct |
383 ms |
468072 KB |
Output is correct |
| 11 |
Correct |
393 ms |
468072 KB |
Output is correct |
| 12 |
Correct |
457 ms |
468072 KB |
Output is correct |
| 13 |
Correct |
503 ms |
468072 KB |
Output is correct |
| 14 |
Correct |
483 ms |
468072 KB |
Output is correct |
| 15 |
Correct |
421 ms |
468072 KB |
Output is correct |
| 16 |
Correct |
402 ms |
468072 KB |
Output is correct |
| 17 |
Correct |
655 ms |
468072 KB |
Output is correct |
| 18 |
Correct |
516 ms |
468072 KB |
Output is correct |
| 19 |
Correct |
511 ms |
468072 KB |
Output is correct |
| 20 |
Correct |
477 ms |
468072 KB |
Output is correct |
| 21 |
Correct |
586 ms |
468072 KB |
Output is correct |
| 22 |
Correct |
678 ms |
468072 KB |
Output is correct |
| 23 |
Correct |
686 ms |
468072 KB |
Output is correct |
| 24 |
Correct |
672 ms |
468072 KB |
Output is correct |
| 25 |
Correct |
1047 ms |
468072 KB |
Output is correct |
| 26 |
Correct |
1389 ms |
502976 KB |
Output is correct |
| 27 |
Correct |
1340 ms |
502976 KB |
Output is correct |
| 28 |
Correct |
1335 ms |
502976 KB |
Output is correct |
| 29 |
Correct |
1230 ms |
502976 KB |
Output is correct |
| 30 |
Correct |
1231 ms |
502976 KB |
Output is correct |
| 31 |
Correct |
1062 ms |
502976 KB |
Output is correct |
| 32 |
Correct |
1188 ms |
502976 KB |
Output is correct |
