#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const int MAXN = 4e3 + 11;
char c[MAXN][MAXN];
int d[MAXN][MAXN];
bool vis[MAXN][MAXN];
int h, w;
bool in(int i, int j){
return 1 <= i && i <= h && 1 <= j && j <= w && c[i][j] != '.';
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
struct point{
int x, y;
bool operator< (const point& o) const {
return x < o.x || x == o.x && y < o.y;
}
};
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
cin >> h >> w;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> c[i][j];
}
}
memset(d, 0x3f, sizeof(d));
d[1][1] = 0;
deque<point> dq; dq.push_back({1, 1});
while(!dq.empty()){
auto [x, y] = dq.front(); dq.pop_front();
if(vis[x][y]) continue; vis[x][y] = true;
for(int dir = 0; dir < 4; dir++){
int nx = x + dx[dir], ny = y + dy[dir];
if(!in(nx, ny)) continue;
if(d[nx][ny] > d[x][y] + (c[x][y] != c[nx][ny])){
d[nx][ny] = d[x][y] + (c[x][y] != c[nx][ny]);
if(c[x][y] == c[nx][ny]){
dq.push_front({nx, ny});
}else{
dq.push_back({nx, ny});
}
}
}
}
int ans = 0;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(c[i][j] != '.') ans = max(ans, d[i][j]);
}
}
cout << ans + 1 << endl;
}
Compilation message
tracks.cpp: In member function 'bool point::operator<(const point&) const':
tracks.cpp:21:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
21 | return x < o.x || x == o.x && y < o.y;
| ~~~~~~~~~^~~~~~~~~~
tracks.cpp: In function 'int32_t main()':
tracks.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | auto [x, y] = dq.front(); dq.pop_front();
| ^
tracks.cpp:39:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
39 | if(vis[x][y]) continue; vis[x][y] = true;
| ^~
tracks.cpp:39:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
39 | if(vis[x][y]) continue; vis[x][y] = true;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
67432 KB |
Output is correct |
| 2 |
Correct |
27 ms |
63380 KB |
Output is correct |
| 3 |
Correct |
24 ms |
63592 KB |
Output is correct |
| 4 |
Correct |
30 ms |
67484 KB |
Output is correct |
| 5 |
Correct |
26 ms |
65596 KB |
Output is correct |
| 6 |
Correct |
22 ms |
63416 KB |
Output is correct |
| 7 |
Correct |
23 ms |
63608 KB |
Output is correct |
| 8 |
Correct |
25 ms |
63772 KB |
Output is correct |
| 9 |
Correct |
24 ms |
63988 KB |
Output is correct |
| 10 |
Correct |
33 ms |
65232 KB |
Output is correct |
| 11 |
Correct |
25 ms |
64836 KB |
Output is correct |
| 12 |
Correct |
33 ms |
65664 KB |
Output is correct |
| 13 |
Correct |
29 ms |
65612 KB |
Output is correct |
| 14 |
Correct |
25 ms |
65620 KB |
Output is correct |
| 15 |
Correct |
37 ms |
67440 KB |
Output is correct |
| 16 |
Correct |
44 ms |
67340 KB |
Output is correct |
| 17 |
Correct |
39 ms |
67296 KB |
Output is correct |
| 18 |
Correct |
29 ms |
67516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
93204 KB |
Output is correct |
| 2 |
Correct |
69 ms |
74692 KB |
Output is correct |
| 3 |
Correct |
315 ms |
110324 KB |
Output is correct |
| 4 |
Correct |
118 ms |
81740 KB |
Output is correct |
| 5 |
Correct |
205 ms |
95664 KB |
Output is correct |
| 6 |
Correct |
675 ms |
123584 KB |
Output is correct |
| 7 |
Correct |
39 ms |
94664 KB |
Output is correct |
| 8 |
Correct |
34 ms |
93268 KB |
Output is correct |
| 9 |
Correct |
24 ms |
63500 KB |
Output is correct |
| 10 |
Correct |
22 ms |
63316 KB |
Output is correct |
| 11 |
Correct |
37 ms |
94060 KB |
Output is correct |
| 12 |
Correct |
22 ms |
64420 KB |
Output is correct |
| 13 |
Correct |
69 ms |
74580 KB |
Output is correct |
| 14 |
Correct |
46 ms |
71260 KB |
Output is correct |
| 15 |
Correct |
48 ms |
72104 KB |
Output is correct |
| 16 |
Correct |
44 ms |
66980 KB |
Output is correct |
| 17 |
Correct |
138 ms |
83092 KB |
Output is correct |
| 18 |
Correct |
101 ms |
82828 KB |
Output is correct |
| 19 |
Correct |
123 ms |
81668 KB |
Output is correct |
| 20 |
Correct |
111 ms |
80388 KB |
Output is correct |
| 21 |
Correct |
200 ms |
96728 KB |
Output is correct |
| 22 |
Correct |
210 ms |
95632 KB |
Output is correct |
| 23 |
Correct |
247 ms |
90528 KB |
Output is correct |
| 24 |
Correct |
228 ms |
96636 KB |
Output is correct |
| 25 |
Correct |
560 ms |
110320 KB |
Output is correct |
| 26 |
Correct |
653 ms |
152908 KB |
Output is correct |
| 27 |
Correct |
706 ms |
128484 KB |
Output is correct |
| 28 |
Correct |
728 ms |
123592 KB |
Output is correct |
| 29 |
Correct |
734 ms |
121256 KB |
Output is correct |
| 30 |
Correct |
666 ms |
126656 KB |
Output is correct |
| 31 |
Correct |
492 ms |
98868 KB |
Output is correct |
| 32 |
Correct |
643 ms |
127104 KB |
Output is correct |
