/**
https://boi2013.informatik-olympiade.de/wp-content/uploads/2013/05/tracks-spoiler.pdf
*/
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;
using namespace std;
typedef long long ll;
long long readInt() {
bool minus1 = false;
long long result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus1 = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus1)
return -result;
else
return result;
}
const int N = 4001;
char a[N][N];
int d[N][N];
int d_x[] = {1, -1, 0, 0};
int d_y[] = {0, 0, 1, -1};
int H, W;
bool norm(int x1, int y1) {
if (x1 >= 1 && y1 >= 1 && x1 <= H && y1 <= W) {
if (a[x1][y1] != '.') {
return 1;
} else {
return 0;
}
} else {
return 0;
}
}
int main() {
#ifdef IZI_KATKA
assert(freopen("input", "r", stdin));
assert(freopen("output", "w", stdout));
#endif
H = readInt(), W = readInt();
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cin >> a[i][j];
d[i][j] = MOD;
}
}
deque<pair <int, int> > q;
q.push_front({1, 1});
d[1][1] = 0;
int mx = 0;
while (!q.empty()) {
pair <int, int> v = q.front();
q.pop_front();
int x = v.F;
int y = v.S;
//cerr << v.F << ' ' << v.S << endl;
for (int i = 0; i < 4; i++) {
int X = v.first + d_x[i];
int Y = v.second + d_y[i];
if (norm(X, Y)) {
if (d[X][Y] > d[x][y] + (a[X][Y] != a[x][y])) {
d[X][Y] = d[x][y] + (a[X][Y] != a[x][y]);
if ((a[X][Y] != a[x][y])) {
q.push_front({X, Y});
} else {
q.pb({X, Y});
}
}
}
}
}
for (int i =1 ; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (a[i][j] != '.')
mx = max(mx, d[i][j]);
//cout << d[i][j] << ' ';
}
//cout << endl;
}
cout << mx+1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2074 ms |
6456 KB |
Time limit exceeded |
2 |
Correct |
2 ms |
6456 KB |
Output is correct |
3 |
Correct |
3 ms |
6456 KB |
Output is correct |
4 |
Correct |
588 ms |
6456 KB |
Output is correct |
5 |
Correct |
111 ms |
6456 KB |
Output is correct |
6 |
Correct |
2 ms |
6456 KB |
Output is correct |
7 |
Correct |
3 ms |
6456 KB |
Output is correct |
8 |
Correct |
7 ms |
6456 KB |
Output is correct |
9 |
Correct |
5 ms |
6456 KB |
Output is correct |
10 |
Correct |
73 ms |
6456 KB |
Output is correct |
11 |
Correct |
72 ms |
6456 KB |
Output is correct |
12 |
Correct |
543 ms |
6456 KB |
Output is correct |
13 |
Correct |
109 ms |
6456 KB |
Output is correct |
14 |
Correct |
122 ms |
6456 KB |
Output is correct |
15 |
Correct |
1945 ms |
7228 KB |
Output is correct |
16 |
Execution timed out |
2074 ms |
7768 KB |
Time limit exceeded |
17 |
Correct |
1115 ms |
7768 KB |
Output is correct |
18 |
Correct |
657 ms |
7768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
32840 KB |
Output is correct |
2 |
Execution timed out |
2064 ms |
32840 KB |
Time limit exceeded |
3 |
Execution timed out |
2041 ms |
92948 KB |
Time limit exceeded |
4 |
Execution timed out |
2052 ms |
92948 KB |
Time limit exceeded |
5 |
Correct |
800 ms |
92948 KB |
Output is correct |
6 |
Execution timed out |
2070 ms |
94280 KB |
Time limit exceeded |
7 |
Correct |
32 ms |
94280 KB |
Output is correct |
8 |
Correct |
33 ms |
94280 KB |
Output is correct |
9 |
Correct |
762 ms |
94280 KB |
Output is correct |
10 |
Correct |
5 ms |
94280 KB |
Output is correct |
11 |
Correct |
31 ms |
94280 KB |
Output is correct |
12 |
Correct |
8 ms |
94280 KB |
Output is correct |
13 |
Execution timed out |
2064 ms |
94280 KB |
Time limit exceeded |
14 |
Execution timed out |
2067 ms |
94280 KB |
Time limit exceeded |
15 |
Correct |
96 ms |
94280 KB |
Output is correct |
16 |
Execution timed out |
2067 ms |
94280 KB |
Time limit exceeded |
17 |
Execution timed out |
2068 ms |
94280 KB |
Time limit exceeded |
18 |
Correct |
397 ms |
94280 KB |
Output is correct |
19 |
Execution timed out |
2053 ms |
94280 KB |
Time limit exceeded |
20 |
Execution timed out |
2075 ms |
94280 KB |
Time limit exceeded |
21 |
Execution timed out |
2037 ms |
94280 KB |
Time limit exceeded |
22 |
Correct |
779 ms |
94280 KB |
Output is correct |
23 |
Execution timed out |
2053 ms |
94280 KB |
Time limit exceeded |
24 |
Correct |
788 ms |
94280 KB |
Output is correct |
25 |
Correct |
1503 ms |
94280 KB |
Output is correct |
26 |
Correct |
1588 ms |
94280 KB |
Output is correct |
27 |
Execution timed out |
2078 ms |
94280 KB |
Time limit exceeded |
28 |
Execution timed out |
2082 ms |
94308 KB |
Time limit exceeded |
29 |
Execution timed out |
2067 ms |
94308 KB |
Time limit exceeded |
30 |
Execution timed out |
2077 ms |
94308 KB |
Time limit exceeded |
31 |
Execution timed out |
2079 ms |
94308 KB |
Time limit exceeded |
32 |
Execution timed out |
2077 ms |
94308 KB |
Time limit exceeded |