#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define inf 1000000000
#define sz(x) (ll)x.size()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair< int , pii> piii;
typedef pair<int,bool> pib;
typedef vector<pii> vii;
typedef vector<pib> vib;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<string,string> pss;
typedef vector<pss> vss;
typedef pair<ld , ld> pdd;
typedef vector<ld> vd;
typedef vector<vector<pib>> vvib;
typedef vector<piii> viii;
typedef vector<viii> vviii;
typedef vector<bool> vb;
typedef pair<pii , bool> piib;
typedef vector<pair<pii , bool>> viib;
const int MOD = 1e9 + 7; //998244353;
struct comp
{
bool operator()(const vi &a, const vi &b)
{
return a[0] > b[0];
}
};
int dirs[4][2] {{-1 , 0} , {0 , -1} , {1, 0} , {0 , 1}};
string grid[1005];
vector<set<int>> cols;
vector<set<int>> rows;
bool v[1005][1005];
int distances[1005][1005];
int closestWall[1005][1005];
int n , m;
void preprocess(){
memset(closestWall , -1 , sizeof closestWall);
queue<piii> bfs;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(grid[i][j] == '#'){
bfs.push({0 , {i , j}});
closestWall[i][j] = 0;
}
}
}
while(bfs.size()){
piii p = bfs.front();
int dis = p.fi;
int x = p.se.fi;
int y = p.se.se;
for(int i = 0;i<4;i++){
int x0 = x + dirs[i][0];
int y0 = y + dirs[i][1];
if(x0 == -1 || y0 == -1 || x0 == n || y0 == m || closestWall[x0][y0] != -1)continue;
closestWall[x0][y0] = dis + 1;
bfs.push({dis + 1 , {x0 , y0}});
}
bfs.pop();
}
}
vi getWalls(int x , int y){
auto pdown = rows[y].upper_bound(x);
int down = *pdown;
pdown--;
int up = *pdown;
auto pright = cols[x].upper_bound(y);
int right = *pright;
pright--;
int left = *pright;
//cout << "WALLS" << up << " " << right << " " << down << " " << left << endl;
vi walls{up+1, y , x,right-1 , down-1 , y , x, left+1};
return walls;
}
int main(){
// freopen("input.txt" , "r" , stdin);
// freopen("output.txt" , "w" , stdout);
cin >> n >> m;
memset(v , 0 , sizeof v);
for(int i = 1;i<=n;i++){
cin >> grid[i];
grid[i] = "#" + grid[i] + "#";
}
grid[0] = grid[n+1] = string(m+2 , '#');
n += 2;
m += 2;
priority_queue<vi , vector<vi> , comp> pq;
int initx , inity , destX , destY;
cols.resize(n);
rows.resize(m);
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
distances[i][j] = inf;
if(grid[i][j] == 'S'){
initx = i;
inity = j;
distances[i][j] = 0;
}
else if(grid[i][j] == 'C'){
destX = i;
destY = j;
}
else if(grid[i][j] == '#'){
cols[i].insert(j);
rows[j].insert(i);
}
}
}
preprocess();
/*for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
cout << closestWall[i][j] << " ";
}
cout << endl;
}*/
vi initState{0 , initx , inity};
pq.push(initState);
while(pq.size()){
vi s = pq.top();
int dis = s[0] , x = s[1] , y = s[2];
pq.pop();
if(v[x][y])continue;
v[x][y] = 1;
//cout << dis << " " << x << " " << y << endl;
if(x == destX && y == destY){
cout << dis << endl;
return 0;
}
for(int i = 0;i<4;i++){
int x0 = x + dirs[i][0];
int y0 = y + dirs[i][1];
if(grid[x0][y0] == '#' || distances[x0][y0] <= dis + 1) continue;
distances[x0][y0] = dis + 1;
pq.push(vi{dis + 1 , x0 , y0});
}
vi walls = getWalls(x , y);
int c = closestWall[x][y];
for(int i = 0;i<8;i+=2){
int x0 = walls[i];
int y0 = walls[i+1];
int dis0 = dis + c;
if(distances[x0][y0] <= dis0)continue;
distances[x0][y0] = dis0;
pq.push(vi{dis0 , x0,y0});
//cout << "queued: " << x0 << " " << y0 << " " <<dis0 << endl;
}
}
}
//NEVER GIVE UP
//LONG LONG
