/**
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 = 4444;
char a[N][N];
bool used[N][N];
int d[N][N];
int timer = 0;
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] != '.' && !used[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];
}
}
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
d[i][j] = MOD;
}
}
deque<pair <int, int> > q;
q.push_front({1, 1});
used[1][1] = true;
d[1][1] = 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});
}
}
}
}
}
int mx = 0;
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 |
2043 ms |
6904 KB |
Time limit exceeded |
| 2 |
Correct |
2 ms |
6904 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6904 KB |
Output is correct |
| 4 |
Correct |
671 ms |
6904 KB |
Output is correct |
| 5 |
Correct |
119 ms |
6904 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6904 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6904 KB |
Output is correct |
| 8 |
Correct |
8 ms |
6904 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6904 KB |
Output is correct |
| 10 |
Correct |
84 ms |
6904 KB |
Output is correct |
| 11 |
Correct |
105 ms |
6904 KB |
Output is correct |
| 12 |
Correct |
606 ms |
6904 KB |
Output is correct |
| 13 |
Correct |
116 ms |
6904 KB |
Output is correct |
| 14 |
Correct |
118 ms |
6904 KB |
Output is correct |
| 15 |
Execution timed out |
2009 ms |
7576 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2061 ms |
8060 KB |
Time limit exceeded |
| 17 |
Correct |
1226 ms |
8060 KB |
Output is correct |
| 18 |
Correct |
639 ms |
8060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
33388 KB |
Output is correct |
| 2 |
Execution timed out |
2051 ms |
33388 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2051 ms |
106904 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2043 ms |
106904 KB |
Time limit exceeded |
| 5 |
Correct |
823 ms |
106904 KB |
Output is correct |
| 6 |
Execution timed out |
2059 ms |
136440 KB |
Time limit exceeded |
| 7 |
Correct |
35 ms |
136440 KB |
Output is correct |
| 8 |
Correct |
33 ms |
136440 KB |
Output is correct |
| 9 |
Correct |
746 ms |
136440 KB |
Output is correct |
| 10 |
Correct |
4 ms |
136440 KB |
Output is correct |
| 11 |
Correct |
34 ms |
136440 KB |
Output is correct |
| 12 |
Correct |
5 ms |
136440 KB |
Output is correct |
| 13 |
Execution timed out |
2049 ms |
136440 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2054 ms |
136440 KB |
Time limit exceeded |
| 15 |
Correct |
128 ms |
136440 KB |
Output is correct |
| 16 |
Execution timed out |
2052 ms |
136440 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2058 ms |
136440 KB |
Time limit exceeded |
| 18 |
Correct |
366 ms |
136440 KB |
Output is correct |
| 19 |
Execution timed out |
2049 ms |
136440 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2056 ms |
136440 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2062 ms |
138540 KB |
Time limit exceeded |
| 22 |
Correct |
790 ms |
145412 KB |
Output is correct |
| 23 |
Execution timed out |
2049 ms |
145412 KB |
Time limit exceeded |
| 24 |
Correct |
751 ms |
163300 KB |
Output is correct |
| 25 |
Correct |
1552 ms |
202684 KB |
Output is correct |
| 26 |
Correct |
1855 ms |
203012 KB |
Output is correct |
| 27 |
Execution timed out |
2073 ms |
229708 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2041 ms |
245552 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2068 ms |
259584 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2075 ms |
264964 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2032 ms |
264964 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2064 ms |
291328 KB |
Time limit exceeded |
