This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 1e3 + 10, MOD = 1e9 + 7;
int R[N][N], L[N][N], U[N][N], D[N][N], A[N][N], pd[N * N], dp[N * N], M[N * N], dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, n, m, st, en;
vector<pii> adj[N * N]; char S[N]; queue<int> Q;
int id(int x, int y) {
return x * (m + 1) + y;
}
inline void add_edge(int u, int v, int w) {
adj[u].push_back({v, w});
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", S + 1);
for (int j = 1; j <= m; j++) {
if (S[j] == '#') A[i][j] = 0;
else if (S[j] == 'S') A[i][j] = 1, st = id(i, j);
else if (S[j] == 'C') A[i][j] = 1, en = id(i, j);
else A[i][j] = 1;
}
}
fill(dp, dp + N * N, MOD);
fill(pd, pd + N * N, MOD);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!A[i][j]) continue;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d], ny = j + dy[d];
if (nx <= 0 || nx > n || ny <= 0 || ny > m || !A[nx][ny]) continue;
add_edge(id(i, j), id(nx, ny), 1);
}
if (SZ(adj[id(i, j)]) != 4) dp[id(i, j)] = 1, Q.push(id(i, j));
}
}
while (SZ(Q)) {
int v = Q.front(); Q.pop();
for (pii u : adj[v]) {
if (dp[u.F] > dp[v] + u.S) {
dp[u.F] = dp[v] + u.S;
Q.push(u.F);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!A[i][j - 1]) L[i][j] = j;
else L[i][j] = L[i][j - 1];
}
for (int j = m; j >= 1; j--) {
if (!A[i][j + 1]) R[i][j] = j;
else R[i][j] = R[i][j + 1];
}
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (!A[i - 1][j]) U[i][j] = i;
else U[i][j] = U[i - 1][j];
}
for (int i = n; i; i--) {
if (!A[i + 1][j]) D[i][j] = i;
else D[i][j] = D[i + 1][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!A[i][j]) continue;
int v = id(i, j), l = id(i, L[i][j]), r = id(i, R[i][j]), u = id(U[i][j], j), d = id(D[i][j], j);
add_edge(v, u, dp[v]);
add_edge(v, l, dp[v]);
add_edge(v, d, dp[v]);
add_edge(v, r, dp[v]);
}
}
priority_queue<pii> pq;
pq.push({pd[st] = 0, st});
while (SZ(pq)) {
int v = pq.top().S; pq.pop();
if (M[v]) continue;
M[v] = 1;
for (pii u : adj[v]) {
if (pd[u.F] > pd[v] + u.S) {
pd[u.F] = pd[v] + u.S;
pq.push({-pd[u.F], u.F});
}
}
}
printf("%d\n", pd[en]);
return 0;
}
Compilation message (stderr)
portals.cpp: In function 'int main()':
portals.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
portals.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | scanf("%s", S + 1);
| ~~~~~^~~~~~~~~~~~~
# | 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... |