//0/1 bfs each element, find max
#include <iostream>
#include <queue>
using namespace std;
using pii = pair<int, int>;
int h,w, ans=1;
string field[4001];
bool used[4001][4001];
pii dir[4] = {{0,1},{1,0},{-1,0},{0,-1}};
pii operator+(pii a, pii b){
return make_pair(a.first+b.first, a.second+b.second);
}
deque<pii> q;
deque<int> moves;
deque<char> sign;
bool out(pii a){
if (a.first < 0 || a.second < 0 || a.first > h || a.second > w) return true;
return false;
}
int main(){
cin >> h >> w;
for (int i=0; i<h; i++){
cin >> field[i];
}
q.push_back({0,0});
moves.push_back(1);
sign.push_back(field[0][0]);
used[0][0] = true;
while (!q.empty()){
pii cur = q.front(); q.pop_front();
int curmove = moves.front(); moves.pop_front();
char cursign = sign.front(); sign.pop_front();
ans = max(ans, curmove);
for (int i=0; i<4; i++){
pii newp = cur + dir[i];
if (out(newp) || field[newp.first][newp.second] == '.' || used[newp.first][newp.second]) continue;
if (field[newp.first][newp.second] == cursign){
sign.push_front(cursign);
moves.push_front(curmove);
q.push_front(newp);
}
else{
sign.push_back(field[newp.first][newp.second]);
moves.push_back(curmove+1);
q.push_back(newp);
}
used[newp.first][newp.second] = true;
}
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
3156 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
3028 KB |
Output isn't correct |
| 5 |
Correct |
5 ms |
1780 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1492 KB |
Output is correct |
| 11 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 12 |
Incorrect |
7 ms |
1864 KB |
Output isn't correct |
| 13 |
Correct |
4 ms |
1748 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1748 KB |
Output is correct |
| 15 |
Correct |
16 ms |
3156 KB |
Output is correct |
| 16 |
Incorrect |
16 ms |
3060 KB |
Output isn't correct |
| 17 |
Correct |
12 ms |
2984 KB |
Output is correct |
| 18 |
Incorrect |
9 ms |
3028 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
15424 KB |
Output isn't correct |
| 2 |
Correct |
62 ms |
9248 KB |
Output is correct |
| 3 |
Correct |
524 ms |
52536 KB |
Output is correct |
| 4 |
Correct |
130 ms |
18592 KB |
Output is correct |
| 5 |
Incorrect |
369 ms |
31444 KB |
Output isn't correct |
| 6 |
Correct |
868 ms |
75924 KB |
Output is correct |
| 7 |
Correct |
15 ms |
16084 KB |
Output is correct |
| 8 |
Incorrect |
15 ms |
15444 KB |
Output isn't correct |
| 9 |
Correct |
4 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
444 KB |
Output is correct |
| 11 |
Correct |
12 ms |
15832 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 13 |
Correct |
63 ms |
9244 KB |
Output is correct |
| 14 |
Correct |
50 ms |
6624 KB |
Output is correct |
| 15 |
Correct |
35 ms |
7168 KB |
Output is correct |
| 16 |
Correct |
35 ms |
3388 KB |
Output is correct |
| 17 |
Correct |
165 ms |
19804 KB |
Output is correct |
| 18 |
Correct |
148 ms |
19748 KB |
Output is correct |
| 19 |
Correct |
128 ms |
18596 KB |
Output is correct |
| 20 |
Correct |
120 ms |
17276 KB |
Output is correct |
| 21 |
Correct |
279 ms |
31936 KB |
Output is correct |
| 22 |
Incorrect |
426 ms |
31388 KB |
Output isn't correct |
| 23 |
Incorrect |
376 ms |
27212 KB |
Output isn't correct |
| 24 |
Correct |
329 ms |
32132 KB |
Output is correct |
| 25 |
Incorrect |
674 ms |
52524 KB |
Output isn't correct |
| 26 |
Incorrect |
775 ms |
115388 KB |
Output isn't correct |
| 27 |
Correct |
830 ms |
122676 KB |
Output is correct |
| 28 |
Correct |
963 ms |
75996 KB |
Output is correct |
| 29 |
Correct |
918 ms |
71456 KB |
Output is correct |
| 30 |
Correct |
889 ms |
84852 KB |
Output is correct |
| 31 |
Incorrect |
661 ms |
33832 KB |
Output isn't correct |
| 32 |
Correct |
830 ms |
90352 KB |
Output is correct |
