#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef unsigned int uint;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 505;
const int inf = 1e9 + 127;
char a[N][N];
int d[N][N];
pii go[N][N][4];
inline void solve () {
int n, m; cin >> n >> m;
pii s, f;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
if (a[i][j] == 'C') s = {i, j};
if (a[i][j] == 'F') f = {i, j};
d[i][j] = inf;
}
}
for (int i = 0; i < n; ++i) {
int lst = -1;
for (int j = 0; j < m; ++j) {
if (a[i][j] == '#') lst = j;
go[i][j][0] = {i, lst + 1};
}
lst = m;
for (int j = m - 1; j >= 0; --j) {
if (a[i][j] == '#') lst = j;
go[i][j][1] = {i, lst - 1};
}
}
for (int j = 0; j < m; ++j) {
int lst = -1;
for (int i = 0; i < n; ++i) {
if (a[i][j] == '#') lst = i;
go[i][j][2] = {lst + 1, j};
}
lst = n;
for (int i = n - 1; i >= 0; --i) {
if (a[i][j] == '#') lst = i;
go[i][j][3] = {lst - 1, j};
}
}
priority_queue <array <int, 3>, vector <array <int, 3>>, greater <array <int, 3>>> pq;
d[s.fr][s.sc] = 0; pq.push({0, s.fr, s.sc});
function <bool(int, int)> valid = [&] (int x, int y) { return x >= 0 && y >= 0 && x < n && y < m; };
function <int(int, int, int, int)> dist = [&] (int x, int y, int xx, int yy) { return abs(x - xx) + abs(y - yy); };
while (sz(pq)) {
auto [dis, x, y] = pq.top(); pq.pop();
if (dis > d[x][y]) continue;
/// little step
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) && a[nx][ny] != '#' && umin(d[nx][ny], d[x][y] + 1)) pq.push({d[nx][ny], nx, ny});
}
/// big step
for (int port1 = 0; port1 < 4; ++port1) {
for (int port2 = 0; port2 < 4; ++port2) {
if (port1 == port2) continue;
auto [qx, qy] = go[x][y][port1];
auto [wx, wy] = go[x][y][port2];
if (umin(d[wx][wy], d[x][y] + dist(x, y, qx, qy) + 1)) pq.push({d[wx][wy], wx, wy});
}
}
}
if (d[f.fr][f.sc] == inf) cout << "nemoguce";
else cout << d[f.fr][f.sc];
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
Compilation message
portal.cpp: In function 'void solve()':
portal.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [dis, x, y] = pq.top(); pq.pop();
| ^
portal.cpp:97:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | auto [qx, qy] = go[x][y][port1];
| ^
portal.cpp:98:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | auto [wx, wy] = go[x][y][port2];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3188 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
7484 KB |
Output is correct |
| 2 |
Correct |
24 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
16 ms |
5076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5908 KB |
Output is correct |
| 4 |
Correct |
32 ms |
6808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
9948 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9688 KB |
Output is correct |
| 3 |
Correct |
47 ms |
9712 KB |
Output is correct |
| 4 |
Correct |
43 ms |
9700 KB |
Output is correct |
