#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define inc(i, l, r, d) for (int i = l; i <= r; i += d)
#define dec(i, r, l, d) for (int i = r; i >= l; i -= d)
#define dbg(x) cerr << #x << " = " << x << endl;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 127397154761;
ll qpow(ll a, ll b) {if (b == 0) return 1; ll ans = qpow(a, b >> 1); ans = ans * ans % mod; if (b & 1) ans = ans * a % mod; return ans;}
using namespace std;
void IOS(string name = "") {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
if ((int)name.size()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
const int maxn = 4005;
map<pii, vector<pair<pii, int>>> g;
int m, n;
char s[maxn][maxn];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
map<pii, int > dis;
map<pii, bool> vis;
bool check(int x1, int y1) {
return x1 > 0 && y1 > 0 && x1 <= m && y1 <= n;
}
void bfs() {
deque<pii> dq;
rep(i, m) {
rep(j, n) {
dis[mk(i, j)] = INT_MAX - 10;
}
}
dis[mk(1, 1)] = 1;
dq.pb(mk(1, 1));
vis[mk(1, 1)] = true;
while (!dq.empty()) {
pii u = dq.front(); dq.pop_front();
for (auto it: g[u]) {
pii v = it.first;
int w = it.second;
if (vis[v]) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
vis[v] = true;
if (w == 1) {
dq.pb(v);
}
else {
dq.push_front(v);
}
}
}
}
}
int main() {
IOS();
cin >> m >> n;
rep(i, m) {
rep(j, n) {
cin >> s[i][j];
}
}
if (s[1][1] == '.') {
cout << 0 << endl;
return 0;
}
rep(i, m) {
rep(j, n) {
forn(k, 4) {
int x1 = i + d[k][0], y1 = j + d[k][1];
if (s[x1][y1] != '.' && check(x1, y1)) {
if (s[x1][y1] == s[i][j]) {
g[mk(i, j)].pb(mk(mk(x1, y1), 0));
}
else {
g[mk(i, j)].pb(mk(mk(x1, y1), 1));
}
}
}
}
}
bfs();
int ans = 0;
rep(i, m) {
rep(j, n) {
if (s[i][j] != '.') {
ans = max(ans, dis[mk(i, j)]);
}
}
}
cout << ans << endl;
return 0;
}
Compilation message
tracks.cpp: In function 'void IOS(std::string)':
tracks.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
446 ms |
65780 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
347 ms |
43248 KB |
Output is correct |
| 5 |
Correct |
55 ms |
12624 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1764 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1964 KB |
Output is correct |
| 10 |
Correct |
54 ms |
12680 KB |
Output is correct |
| 11 |
Correct |
69 ms |
11860 KB |
Output is correct |
| 12 |
Correct |
157 ms |
24152 KB |
Output is correct |
| 13 |
Correct |
54 ms |
12624 KB |
Output is correct |
| 14 |
Correct |
59 ms |
12628 KB |
Output is correct |
| 15 |
Correct |
376 ms |
59468 KB |
Output is correct |
| 16 |
Correct |
497 ms |
65876 KB |
Output is correct |
| 17 |
Correct |
283 ms |
45128 KB |
Output is correct |
| 18 |
Correct |
346 ms |
43092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
23120 KB |
Output is correct |
| 2 |
Correct |
1897 ms |
282192 KB |
Output is correct |
| 3 |
Execution timed out |
2095 ms |
884560 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2063 ms |
411988 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2086 ms |
772692 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2094 ms |
406944 KB |
Time limit exceeded |
| 7 |
Correct |
32 ms |
22872 KB |
Output is correct |
| 8 |
Correct |
30 ms |
23124 KB |
Output is correct |
| 9 |
Correct |
49 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5208 KB |
Output is correct |
| 11 |
Correct |
24 ms |
21340 KB |
Output is correct |
| 12 |
Correct |
19 ms |
5428 KB |
Output is correct |
| 13 |
Correct |
1841 ms |
282192 KB |
Output is correct |
| 14 |
Correct |
1052 ms |
164304 KB |
Output is correct |
| 15 |
Correct |
1123 ms |
170784 KB |
Output is correct |
| 16 |
Correct |
1008 ms |
130384 KB |
Output is correct |
| 17 |
Execution timed out |
2070 ms |
626204 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2070 ms |
600400 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2029 ms |
411472 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2097 ms |
498492 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2056 ms |
853500 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2067 ms |
796496 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2133 ms |
884816 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2108 ms |
864080 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2051 ms |
647844 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2056 ms |
422512 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2076 ms |
427436 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2039 ms |
400564 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2076 ms |
402096 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2045 ms |
383016 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2063 ms |
621724 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2092 ms |
737620 KB |
Time limit exceeded |
