#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define ALL(v) (v).begin(), (v).end()
#define popcount(x) __builtin_popcount(x)
#define setp(x) setprecision(x)
#define MASK(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ID(x, y) ((x - 1) * m + y)
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
const int NM = 1e6 + 10;
int n, m, start, target;
char a[NM];
ll dp[NM];
vector<pii> edges[NM];
set<pii> r[1005], c[1005];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
struct Data {
int x, y, cost;
bool inline operator < (const Data &A) const {
return cost > A.cost;
}
};
bool check(int x, int y) {
return (x <= n && x > 0 && y <= m && y > 0 && a[ID(x, y)] != '#');
}
void xuli() {
priority_queue<Data> pq;
memset(dp, INF, sizeof dp);
dp[start] = 0;
int xstart = start / m + 1, ystart = start % m;
for(int i = 0; i < 4; i++) {
int u = xstart + dx[i];
int v = ystart + dy[i];
if(!check(u, v)) continue;
if(minimize(dp[ID(u, v)], 1))
pq.push({u, v, dp[ID(u, v)]});
}
auto it = r[xstart].upper_bound({ystart, INF});
it--;
pii cur = *it;
if(minimize(dp[ID(xstart, cur.fi)], min(ystart - cur.fi, cur.se - ystart) + 1))
pq.push({xstart, cur.fi, dp[ID(xstart, cur.fi)]});
if(minimize(dp[ID(xstart, cur.se)], min(ystart - cur.fi, cur.se - ystart) + 1))
pq.push({xstart, cur.se, dp[ID(xstart, cur.se)]});
auto it2 = c[ystart].upper_bound({xstart, INF});
it2--;
pii cur2 = *it2;
if(minimize(dp[ID(cur2.fi, ystart)], min(xstart - cur2.fi, cur2.se - xstart) + 1))
pq.push({cur2.fi, ystart, dp[ID(cur2.fi, ystart)]});
if(minimize(dp[ID(cur2.se, ystart)], min(xstart - cur2.fi, cur2.se - xstart) + 1))
pq.push({cur2.se, ystart, dp[ID(cur2.se, ystart)]});
while(pq.size()) {
Data u = pq.top();
pq.pop();
if(u.cost != dp[ID(u.x, u.y)]) continue;
int curId = ID(u.x, u.y);
if(curId == target) break;
for(int i = 0; i < 4; i++) {
int x = u.x + dx[i];
int y = u.y + dy[i];
if(!check(x, y)) continue;
if(minimize(dp[ID(x, y)], u.cost + 1)) {
pq.push({x, y, dp[ID(x, y)]});
}
}
auto tmp = r[u.x].upper_bound({u.y, INF});
tmp--;
pii tam = *tmp;
if(minimize(dp[ID(u.x, tam.fi)], u.cost + min(u.y - tam.fi, tam.se - u.y) + 1)) {
pq.push({u.x, tam.fi, dp[ID(u.x, tam.fi)]});
}
if(minimize(dp[ID(u.x, tam.se)], u.cost + min(u.y - tam.fi, tam.se - u.y) + 1)) {
pq.push({u.x, tam.se, dp[ID(u.x, tam.se)]});
}
auto tmp2 = c[u.y].upper_bound({u.x, INF});
tmp2--;
pii tam2 = *tmp2;
if(minimize(dp[ID(tam2.fi, u.y)], u.cost + min(u.x - tam2.fi, tam2.se - u.x) + 1)) {
pq.push({tam2.fi, u.y, dp[ID(tam2.fi, u.y)]});
}
if(minimize(dp[ID(tam2.se, u.y)], u.cost + min(u.x - tam2.fi, tam2.se - u.x) + 1)) {
pq.push({tam2.se, u.y, dp[ID(tam2.se, u.y)]});
}
}
int res = INF;
cout << dp[target];
}
int main()
{
FastIO
cin >> n >> m;
for(int i = 1; i <= n; i++) {
r[i].insert({1, m});
r[i].insert({INF, INF});
}
for(int i = 1; i <= m; i++) {
c[i].insert({1, n});
c[i].insert({INF, INF});
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char u; cin >> u;
a[(i - 1) * m + j] = u;
if(u == 'S') start = (i - 1) * m + j;
if(u == 'C') target = (i - 1) * m + j;
if(u == '#') {
auto it = r[i].upper_bound({j, INF});
it--;
pii cur = *it;
r[i].erase(it);
if(cur.fi <= j - 1) {
int u1 = cur.fi, u2 = j - 1;
r[i].insert({cur.fi, j - 1});
}
if(cur.se >= j + 1) {
int u1 = j + 1, u2 = cur.se;
r[i].insert({j + 1, cur.se});
}
auto it2 = c[j].upper_bound({i, INF});
it2--;
pii tmp = *it2;
c[j].erase(it2);
if(tmp.fi <= i - 1) {
c[j].insert({tmp.fi, i - 1});
}
if(tmp.se >= i + 1) {
c[j].insert({i + 1, tmp.se});
}
}
}
}
/**
for(int i = 1; i <= n; i++) {
for(pii u : c[i]) cout << u.fi << " " << u.se << " | ";
cout << '\n';
}
**/
xuli();
return 0;
}
Compilation message
portals.cpp: In function 'void xuli()':
portals.cpp:3:13: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
3 | #define INF 0x3f3f3f3f3f3f3f3f
| ^~~~~~~~~~~~~~~~~~
portals.cpp:47:16: note: in expansion of macro 'INF'
47 | memset(dp, INF, sizeof dp);
| ^~~
portals.cpp:55:39: warning: narrowing conversion of 'dp[(((u - 1) * m) + v)]' from 'long long int' to 'int' [-Wnarrowing]
55 | pq.push({u, v, dp[ID(u, v)]});
| ~~~~~~~~~~~^
portals.cpp:62:55: warning: narrowing conversion of 'dp[(((xstart - 1) * m) + cur.std::pair<int, int>::first)]' from 'long long int' to 'int' [-Wnarrowing]
62 | pq.push({xstart, cur.fi, dp[ID(xstart, cur.fi)]});
| ~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:64:55: warning: narrowing conversion of 'dp[(((xstart - 1) * m) + cur.std::pair<int, int>::second)]' from 'long long int' to 'int' [-Wnarrowing]
64 | pq.push({xstart, cur.se, dp[ID(xstart, cur.se)]});
| ~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:70:57: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::first - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
70 | pq.push({cur2.fi, ystart, dp[ID(cur2.fi, ystart)]});
| ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:72:57: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::second - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
72 | pq.push({cur2.se, ystart, dp[ID(cur2.se, ystart)]});
| ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:88:43: warning: narrowing conversion of 'dp[(((x - 1) * m) + y)]' from 'long long int' to 'int' [-Wnarrowing]
88 | pq.push({x, y, dp[ID(x, y)]});
| ~~~~~~~~~~~^
portals.cpp:96:53: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::first)]' from 'long long int' to 'int' [-Wnarrowing]
96 | pq.push({u.x, tam.fi, dp[ID(u.x, tam.fi)]});
| ~~~~~~~~~~~~~~~~~~^
portals.cpp:99:53: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::second)]' from 'long long int' to 'int' [-Wnarrowing]
99 | pq.push({u.x, tam.se, dp[ID(u.x, tam.se)]});
| ~~~~~~~~~~~~~~~~~~^
portals.cpp:106:55: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::first - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
106 | pq.push({tam2.fi, u.y, dp[ID(tam2.fi, u.y)]});
| ~~~~~~~~~~~~~~~~~~~^
portals.cpp:109:55: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::second - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
109 | pq.push({tam2.se, u.y, dp[ID(tam2.se, u.y)]});
| ~~~~~~~~~~~~~~~~~~~^
portals.cpp:3:13: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
3 | #define INF 0x3f3f3f3f3f3f3f3f
| ^~~~~~~~~~~~~~~~~~
portals.cpp:113:15: note: in expansion of macro 'INF'
113 | int res = INF;
| ^~~
portals.cpp:113:9: warning: unused variable 'res' [-Wunused-variable]
113 | int res = INF;
| ^~~
portals.cpp: In function 'int main()':
portals.cpp:143:25: warning: unused variable 'u1' [-Wunused-variable]
143 | int u1 = cur.fi, u2 = j - 1;
| ^~
portals.cpp:143:38: warning: unused variable 'u2' [-Wunused-variable]
143 | int u1 = cur.fi, u2 = j - 1;
| ^~
portals.cpp:147:25: warning: unused variable 'u1' [-Wunused-variable]
147 | int u1 = j + 1, u2 = cur.se;
| ^~
portals.cpp:147:37: warning: unused variable 'u2' [-Wunused-variable]
147 | int u1 = j + 1, u2 = cur.se;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 2 |
Runtime error |
41 ms |
64044 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
31696 KB |
Output is correct |
| 2 |
Runtime error |
46 ms |
64116 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
31728 KB |
Output is correct |
| 2 |
Runtime error |
44 ms |
64024 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 2 |
Runtime error |
41 ms |
64012 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 2 |
Runtime error |
40 ms |
64108 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
