#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 1005,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],dw[N][N];
ar<int,2> rht[N][N],lft[N][N],down[N][N],up[N][N];
char a[N][N];
bool valid(int x,int y) {
return (x > 0 && y > 0 && x <= n && y <= m);
}
void comp(){
// left & right
for (int i = 1; i <= n;i++) {
int x,y;
x = y = -1;
// left
for (int j = m; j > 0;j--) {
if (a[i][j] == '#') x = y = -1;
else if (x == -1) x = i, y = j;
lft[i][j] = {x,y};
}
//right
x = y = -1;
for (int j = 1; j <= m;j++) {
if (a[i][j] == '#') x = y = -1;
else if (x == -1) x = i , y = j;
rht[i][j] = {x,y};
}
}
for (int j = 1; j <= m;j++) {
int x,y;
x = y = -1;
// up
for (int i = n; i > 0;i--) {
if (a[i][j] == '#') x = y = -1;
else if (x == -1) x = i , y = j;
up[i][j] = {x,y};
}
// down
x = y = -1;
for (int i = 1; i <= n;i++) {
if (a[i][j] == '#') x = y = -1;
else if (x == -1) x = i , y = j;
down[i][j] = {x,y};
}
}
}
void bfs() {
queue<ar<int,2>> q;
memset(dw,inf,sizeof(dw));
for (int i = 1; i <= n;i++) {
for (int j = 1; j <= m;j++) {
if (a[i][j] == '#') continue;
for (int dr = 0; dr < 4;dr++) {
int ni = i + rc[dr] ,nj = j + cc[dr];
if (valid(ni,nj) && a[ni][nj] == '#') {
q.push({i,j});
dw[i][j] = 0;
}
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4;i++) {
int nx = x + rc[i] , ny = y + cc[i];
if (valid(nx,ny) && a[nx][ny] != '#' && dw[nx][ny] > dw[x][y] + 1) {
q.push({nx,ny});
dw[nx][ny] = dw[x][y] + 1;
}
}
}
}
void dijkstra() {
memset(d,inf,sizeof(d));
priority_queue<ar<int,3>> pq;
pq.push({0,sx,sy});
d[sx][sy] = 0;
while (!pq.empty()) {
auto [w,x,y] = pq.top();
pq.pop();
if (-w != d[x][y]) continue;
for (auto v : {lft,rht,up,down}) {
auto [nx,ny] = v[x][y];
int cost = d[x][y] + dw[x][y] + 1;
if (valid(nx,ny) && a[nx][ny] != '#' && d[nx][ny] > cost) {
pq.push({-(d[nx][ny] = cost),nx,ny});
}
}
for (int i = 0;i < 4;i++) {
int nx = x + rc[i],ny = y + cc[i];
int cost = d[x][y] + 1;
if (valid(nx,ny) && a[nx][ny] != '#' && d[nx][ny] > cost){
pq.push({-(d[nx][ny] = cost),nx,ny});
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n;i++) {
for (int j = 1; 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();
// cerr << dw[sx][sy];
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... |