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>
using namespace std;
#define pb push_back
#define lwb lower_bound
const int N = 2e6, MX = 1e3+5;
int dx[] = {0, 1};
int dy[] = {1, 0};
vector<array<int, 2>> g[N];
int di[N];
bool vis[N];
char a[MX][MX];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int R, C;
cin >> R >> C;
int XS, YS, XE, YE;
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
cin >> a[i][j];
if (a[i][j] == 'S') {
XS = i, YS = j;
}
if (a[i][j] == 'C') {
XE = i, YE = j;
}
}
}
auto ok = [&](int x, int y) {
return x != 0 && y != 0 && x != R+1 && y != C+1 && a[x][y] != '#';
};
auto h = [&](int x, int y) {
return x * 1001 + y;
};
auto add = [&](int x1, int y1, int x2, int y2, int w) { // (x1, y1) ->(w) (x2, y2)
g[h(x1, y1)].pb({h(x2, y2), w});
};
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
for (int k = 0; k < 2; ++k) {
if (ok(i + dx[k], j + dy[k]) && ok(i, j)) {
add(i, j, i + dx[k], j + dy[k], 1);
add(i + dx[k], j + dy[k], i, j, 1);
}
}
}
}
vector<int> H[R+1], V[C+1];
for (int i = 1; i <= R; ++i) H[i].pb(0);
for (int j = 1; j <= C; ++j) V[j].pb(0);
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
if (a[i][j] == '#') {
H[i].pb(j);
V[j].pb(i);
}
}
}
for (int i = 1; i <= R; ++i) H[i].pb(C+1);
for (int j = 1; j <= C; ++j) V[j].pb(R+1);
for (int i = 1; i <= R; ++i) sort(H[i].begin(), H[i].end());
for (int j = 1; j <= C; ++j) sort(V[j].begin(), V[j].end());
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
if (a[i][j] == '#') continue;
int L = *prev(lwb(H[i].begin(), H[i].end(), j));
int R = *lwb(H[i].begin(), H[i].end(), j);
int D = *lwb(V[j].begin(), V[j].end(), i);
int U = *prev(lwb(V[j].begin(), V[j].end(), i));
int t = min({j - L, R - j, i - U, D - i});
add(i, j, i, L+1, t);
add(i, j, i, R-1, t);
add(i, j, D-1, j, t);
add(i, j, U+1, j, t);
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, h(XS, YS)});
fill(di, di + N, 1e9);
di[h(XS, YS)] = 0;
while (!pq.empty()) {
auto [d, s] = pq.top();
pq.pop();
if (vis[s]) continue;
vis[s] = 1;
for (auto [u, w] : g[s]) {
if (di[u] > w + d) {
di[u] = w + d;
pq.push({di[u], u});
}
}
}
// cout << di[h(2, 8)] << '\n';
// cout << di[h(2, 7)] << '\n';
cout << di[h(XE, YE)] << '\n';
}
Compilation message (stderr)
portals.cpp: In function 'int main()':
portals.cpp:35:31: warning: 'YE' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | return x * 1001 + y;
| ^
portals.cpp:35:22: warning: 'XE' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | return x * 1001 + y;
| ~~^~~~~~
portals.cpp:35:22: warning: 'XS' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | return x * 1001 + y;
| ~~^~~~~~
portals.cpp:35:31: warning: 'YS' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | return x * 1001 + y;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |