#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 1003;
const int inf = 1e9+ 5;
const int rc[]{0,0,1,-1};
const int cc[]{1,-1,0,0}; // right , left, down , up
int n,m,sx,sy,cx,cy,d[N][N];
ar<int,2> tel[N][N][4],near[N][N][4];
char a[N][N];
void comp() {
// left & right
for (int i = 0; i < n;i++) {
int x,y;
x = y = -1;
for (int j = m - 1; j >= 0;j--) {
tel[i][j][1] = {x,y};
if (a[i][j] == '#') {
x = i , y = j;
}
}
x = y = -1;
for (int j = 0; j < m;j++) {
tel[i][j][0] = {x,y};
if (a[i][j] == '#') x = i, y = j;
}
}
// up & down
for (int j = 0; j < m;j++) {
int x,y;
x = y = -1;
for (int i = n - 1; i >= 0;i--) {
tel[i][j][3] = {x,y};
if (a[i][j] == '#') x = i, y = j;
}
x = y = -1;
for (int i = 0; i < n;i++) {
tel[i][j][2] = {x,y};
if (a[i][j] == '#') x = i, y = j;
}
}
}
bool valid(int x,int y) {
return (x >= 0 && y >= 0 && x < n && y < m);
}
void bfs() {
queue<ar<int,3>> q;
for (int i = 0; i < n;i++) {
for (int j = 0; j < m;j++) {
for (int t = 0; t < 4;t++) near[i][j][t] = {-1,-1};
if (a[i][j] == '#') continue;
for (int t = 0; t < 4; t++) {
int ni = i + rc[t],nj = j + cc[t];
if (valid(ni,nj) && a[ni][nj] == '#') {
q.push({i,j,t});
near[i][j][t] = {ni,nj};
}
}
}
}
while (!q.empty()) {
auto [x,y,t] = q.front();
q.pop();
if (valid(x + rc[t ^ 1],y + cc[t ^ 1]) && a[x + rc[t ^ 1]][y + cc[t ^ 1]] != '#') {
near[x + rc[t ^ 1]][y + cc[t ^ 1]][t] = near[x][y][t];
q.push({x + rc[t ^ 1],y + cc[t ^ 1],t});
}
}
}
void dijkstra() {
memset(d,inf,sizeof(d));
d[sx][sy] = 0;
priority_queue<ar<int,3>> pq;
pq.push({0,sx,sy});
while (!pq.empty()) {
auto [w,x,y] = pq.top();
pq.pop();
if (-w != d[x][y]) continue;
for (int i = 0; i < 4;i++) {
int nx = x + rc[i], ny = y + cc[i];
if (valid(nx,ny) && a[nx][ny] != '#' && d[nx][ny] > d[x][y] + 1) {
pq.push({-(d[nx][ny] = d[x][y] + 1),nx,ny});
}
}
for (int i = 0; i < 4;i++) {
auto [wx, wy] = near[x][y][i];
if (valid(wx,wy)) {
for (int j = 0; j < 4;j++) {
auto [nx, ny] = tel[wx][wy][j];
if (valid(nx, ny) && d[nx][ny] > d[x][y] + 1 + abs(wx - x) + abs(wy - y)) {
pq.push({-(d[nx][ny] = d[x][y] + abs(wx - x) + abs(wy - y)),nx,ny});
}
}
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n;i++) {
for (int j = 0; j < m;j++) {
cin >> a[i][j];
if (a[i][j] == 'S') sx = i, sy = j;
if (a[i][j] == 'C') cx = i, cy = j;
}
}
comp();
bfs();
dijkstra();
cout << d[cx][cy];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << "\n";
}
return 0;
}
# | 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... |