| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 654967 | KiriLL1ca | Portal (COCI17_portal) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>;
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;
}