// boi2013 day2 p2
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion
using grid_t = vector<string>;
const vi16 dx = {1, -1, 0, 0};
const vi16 dy = {0, 0, 1, -1};
bool inside(p32 a, int row, int col)
{
return a.first >= 0 && a.first < row &&
a.second >= 0 && a.second < col;
}
int main()
{
#ifndef _AAAAAAAAA
ios_base::sync_with_stdio(false);
cin.tie(0);
#else
freopen("tracks.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int row, col;
cin >> row >> col;
grid_t grid(row);
for (auto &r : grid)
{
cin >> r;
}
vvi32 dist(row, vi32(col, INT_MAX));
dist[0][0] = 1;
deque<p32> q;
q.emplace_back(0, 0);
int ans = 1;
while (!q.empty())
{
auto [r, c] = q.front();
q.pop_front();
for (int i = 0; i < (int)dx.size(); i++)
{
int n_r = r + dx[i];
int n_c = c + dy[i];
if (!inside({n_r, n_c}, row, col) ||
dist[n_r][n_c] != INT_MAX ||
grid[n_r][n_c] == '.')
{
continue;
}
if (grid[r][c] == grid[n_r][n_c])
{
dist[n_r][n_c] = dist[r][c];
ans = max(ans, dist[n_r][n_c]);
q.emplace_front(n_r, n_c);
}
else
{
dist[n_r][n_c] = dist[r][c] + 1;
ans = max(ans, dist[n_r][n_c]);
q.emplace_back(n_r, n_c);
}
}
}
cout << ans << '\n';
return 0;
}
Compilation message
tracks.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
9 | #pragma region dalykai
|
tracks.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
33 | #pragma endregion
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1748 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
6 ms |
1460 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
844 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
848 KB |
Output is correct |
15 |
Correct |
8 ms |
1748 KB |
Output is correct |
16 |
Correct |
10 ms |
1744 KB |
Output is correct |
17 |
Correct |
7 ms |
1676 KB |
Output is correct |
18 |
Correct |
6 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
724 KB |
Output is correct |
2 |
Correct |
33 ms |
8276 KB |
Output is correct |
3 |
Correct |
162 ms |
81272 KB |
Output is correct |
4 |
Correct |
48 ms |
19324 KB |
Output is correct |
5 |
Correct |
122 ms |
45672 KB |
Output is correct |
6 |
Correct |
494 ms |
94904 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
32 ms |
8212 KB |
Output is correct |
14 |
Correct |
17 ms |
5004 KB |
Output is correct |
15 |
Correct |
12 ms |
5460 KB |
Output is correct |
16 |
Correct |
15 ms |
3640 KB |
Output is correct |
17 |
Correct |
83 ms |
20864 KB |
Output is correct |
18 |
Correct |
77 ms |
20660 KB |
Output is correct |
19 |
Correct |
53 ms |
19224 KB |
Output is correct |
20 |
Correct |
40 ms |
17744 KB |
Output is correct |
21 |
Correct |
110 ms |
47420 KB |
Output is correct |
22 |
Correct |
117 ms |
45740 KB |
Output is correct |
23 |
Correct |
189 ms |
39436 KB |
Output is correct |
24 |
Correct |
101 ms |
46244 KB |
Output is correct |
25 |
Correct |
324 ms |
81276 KB |
Output is correct |
26 |
Correct |
289 ms |
112388 KB |
Output is correct |
27 |
Correct |
424 ms |
107804 KB |
Output is correct |
28 |
Correct |
493 ms |
94824 KB |
Output is correct |
29 |
Correct |
504 ms |
93376 KB |
Output is correct |
30 |
Correct |
448 ms |
97456 KB |
Output is correct |
31 |
Correct |
464 ms |
52624 KB |
Output is correct |
32 |
Correct |
354 ms |
96356 KB |
Output is correct |