#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define eb emplace
using namespace std;
struct spInfo{
int distance, row, column;
spInfo() {}
spInfo(int _distance, int _row, int _column) {
distance = _distance; row = _row; column = _column;
}
};
bool operator <(const spInfo &x, const spInfo &y) {
return (x.distance > y.distance);
}
int xCoordinate[4] = {-1,0,0,1};
int yCoordinate[4] = {0,-1,1,0};
int numRow,numColumn;
pair<int,int> cakeCoordinate,mainCoordinate;
vector<vector<char> > labyrinth;
vector<vector<int> > distances;
void fastIO() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
void Read() {
cin >> numRow >> numColumn;
labyrinth.resize(numRow);
for (int row = 0; row < numRow; ++row) labyrinth[row].resize(numColumn);
for (int row = 0; row < numRow; ++row)
for (int column = 0; column < numColumn; ++column) {
cin >> labyrinth[row][column];
if (labyrinth[row][column] == 'S') mainCoordinate = {row, column};
if (labyrinth[row][column] == 'C') cakeCoordinate = {row, column};
}
}
void calculate() {
vector<vector<int> > nearestSide;
auto buildNearestSide = [&] () -> void {
nearestSide.resize(numRow);
for (int row = 0; row < numRow; ++row) nearestSide[row].resize(numColumn);
for (int row = 0; row < numRow; ++row)
for (int column = 0; column < numColumn; ++column) {
if (labyrinth[row][column] == '#') {
nearestSide[row][column] = -1;
continue;
}
nearestSide[row][column] = (int)1e9;
for (int direction = 0; direction < 4; ++direction) {
int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') {
nearestSide[row][column] = 0;
break;
}
}
}
queue<pair<int,int> > myQueue;
for (int row = 0; row < numRow; ++row)
for (int column = 0; column < numColumn; ++column)
if (nearestSide[row][column] == 0) myQueue.emplace(row, column);
while (!myQueue.empty()) {
auto [row, column] = myQueue.front(); myQueue.pop();
for (int direction = 0; direction < 4; ++direction) {
int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn) continue;
if (nearestSide[adjRow][adjColumn] > nearestSide[row][column] + 1) {
nearestSide[adjRow][adjColumn] = nearestSide[row][column] + 1;
myQueue.emplace(adjRow, adjColumn);
}
}
}
};
vector<vector<int> > leftMostWall, rightMostWall, topMostWall, bottomMostWall;
auto buildNearestWall = [&] () -> void {
leftMostWall.resize(numRow); rightMostWall.resize(numRow);
for (int row = 0; row < numRow; ++row) {
leftMostWall[row].resize(numColumn);
rightMostWall[row].resize(numColumn);
}
for (int row = 0; row < numRow; ++row) {
int lastColumn = -1;
for (int column = 0; column < numColumn; ++column)
if (labyrinth[row][column] == '#') lastColumn = column;
else leftMostWall[row][column] = column - lastColumn;
lastColumn = numColumn;
for (int column = numColumn - 1; column >= 0; --column)
if (labyrinth[row][column] == '#') lastColumn = column;
else rightMostWall[row][column] = lastColumn - column;
}
topMostWall.resize(numRow); bottomMostWall.resize(numRow);
for (int row = 0; row < numRow; ++row) {
topMostWall[row].resize(numColumn);
bottomMostWall[row].resize(numColumn);
}
for (int column = 0; column < numColumn; ++column) {
int lastRow = -1;
for (int row = 0; row < numRow; ++row)
if (labyrinth[row][column] == '#') lastRow = row;
else topMostWall[row][column] = row - lastRow;
lastRow = numRow;
for (int row = numRow - 1; row >= 0; --row)
if (labyrinth[row][column] == '#') lastRow = row;
else bottomMostWall[row][column] = lastRow - row;
}
};
buildNearestSide();
buildNearestWall();
auto buildDistance = [&] () -> void {
priority_queue<spInfo> prioQueue;
distances.resize(numRow);
for (int row = 0; row < numRow; ++row) distances[row].resize(numColumn, (int)1e9);
distances[mainCoordinate.first][mainCoordinate.second] = 0;
prioQueue.emplace(0, mainCoordinate.first, mainCoordinate.second);
auto updatePrioQueue = [&] (int row, int column, int val) -> void{
if (distances[row][column] > val) {
distances[row][column] = val;
prioQueue.emplace(distances[row][column], row, column);
}
};
while (!prioQueue.empty()) {
auto [distance, row, column] = prioQueue.top(); prioQueue.pop();
if (distances[row][column] != distance) continue;
for (int direction = 0; direction < 4; ++direction) {
int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') continue;
updatePrioQueue(adjRow, adjColumn, distance + 1);
}
int xTeleport, yTeleport;
xTeleport = row; yTeleport = column - leftMostWall[row][column] + 1;
updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
xTeleport = row; yTeleport = column + rightMostWall[row][column] - 1;
updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
xTeleport = row - topMostWall[row][column] + 1; yTeleport = column;
updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
xTeleport = row + bottomMostWall[row][column] - 1; yTeleport = column;
updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
}
};
buildDistance();
}
void printAnswer() {
cout << distances[cakeCoordinate.first][cakeCoordinate.second] <<'\n';
}
int main() {
fastIO();
Read();
calculate();
printAnswer();
return 0;
}
