#define taskname "1"
#include <bits/stdc++.h>
#define iii tuple<int,int,int>
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, maxn = 4010;
int a[maxn][maxn], d[maxn][maxn], w, h;
deque<iii> dq;
bool val(int i, int j) {return min(i, j) >= 1 && i <= w && j <= h && a[i][j] != -1;}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
//freopen("1.inp", "r", stdin);
cin>>w>>h;
char c;
for (int i=1; i<=w; i++) for (int j=1; j<=h; j++) cin>>c, a[i][j] = c != '.' ? c : -1, d[i][j] = maxn * maxn;
d[1][1] = 1;
dq.emplace_back(1, 1, 1);
while (!dq.empty())
{
auto [i, j, dij] = dq.front(); dq.pop_front();
if (dij != d[i][j]) continue;
for (int k=0; k<4; k++)
{
int ci = i + dx[k], cj = j + dy[k];
if (val(ci, cj))
{
int wt = a[i][j] != a[ci][cj];
if (dij + wt < d[ci][cj])
{
d[ci][cj] = dij + wt;
if (wt) dq.emplace_back(ci, cj, dij+wt);
else dq.emplace_front(ci, cj, dij+wt);
}
}
}
}
int ans = -1;
for (int i=1; i<=w; i++) for (int j=1; j<=h; j++) if (a[i][j] != -1) ans = max(ans, d[i][j]);
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6484 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
9 ms |
5956 KB |
Output is correct |
5 |
Correct |
4 ms |
3284 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
844 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
3 ms |
2900 KB |
Output is correct |
11 |
Correct |
3 ms |
2388 KB |
Output is correct |
12 |
Correct |
6 ms |
3416 KB |
Output is correct |
13 |
Correct |
4 ms |
3284 KB |
Output is correct |
14 |
Correct |
4 ms |
3284 KB |
Output is correct |
15 |
Correct |
13 ms |
6484 KB |
Output is correct |
16 |
Correct |
15 ms |
6492 KB |
Output is correct |
17 |
Correct |
11 ms |
6232 KB |
Output is correct |
18 |
Correct |
8 ms |
5976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31444 KB |
Output is correct |
2 |
Correct |
54 ms |
23644 KB |
Output is correct |
3 |
Correct |
366 ms |
127552 KB |
Output is correct |
4 |
Correct |
123 ms |
46288 KB |
Output is correct |
5 |
Correct |
249 ms |
96040 KB |
Output is correct |
6 |
Correct |
759 ms |
148272 KB |
Output is correct |
7 |
Correct |
14 ms |
32816 KB |
Output is correct |
8 |
Correct |
15 ms |
31444 KB |
Output is correct |
9 |
Correct |
3 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
15 ms |
32308 KB |
Output is correct |
12 |
Correct |
1 ms |
1640 KB |
Output is correct |
13 |
Correct |
60 ms |
23424 KB |
Output is correct |
14 |
Correct |
37 ms |
15480 KB |
Output is correct |
15 |
Correct |
42 ms |
16832 KB |
Output is correct |
16 |
Correct |
28 ms |
9200 KB |
Output is correct |
17 |
Correct |
136 ms |
49848 KB |
Output is correct |
18 |
Correct |
113 ms |
49224 KB |
Output is correct |
19 |
Correct |
111 ms |
46388 KB |
Output is correct |
20 |
Correct |
90 ms |
42900 KB |
Output is correct |
21 |
Correct |
250 ms |
99436 KB |
Output is correct |
22 |
Correct |
237 ms |
96336 KB |
Output is correct |
23 |
Correct |
299 ms |
80648 KB |
Output is correct |
24 |
Correct |
221 ms |
98252 KB |
Output is correct |
25 |
Correct |
543 ms |
127664 KB |
Output is correct |
26 |
Correct |
468 ms |
186076 KB |
Output is correct |
27 |
Correct |
629 ms |
178688 KB |
Output is correct |
28 |
Correct |
738 ms |
148356 KB |
Output is correct |
29 |
Correct |
815 ms |
144656 KB |
Output is correct |
30 |
Correct |
727 ms |
153484 KB |
Output is correct |
31 |
Correct |
589 ms |
103144 KB |
Output is correct |
32 |
Correct |
581 ms |
163572 KB |
Output is correct |