# r802. B. The Phase-Swapped Labyrinth
## 提示
1. 起點在(0,0) 終點在(n-1,m-1)
2. `.` phase 0可以走
3. `#` phase 1可以走
4. 題目的```overlapping``` 表示遇到`S`之後會同步進行兩種Phase
5. 實作即可(bfs)
# 程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0),cin.tie(0);
#define pb push_back
#define yn(a) (a?"Yes\n":"No\n")

signed main(){
    idonthavegirlfriend
    int n,m;
    cin>>n>>m;

    vector<string> mp(n);
    for(auto &i:mp) cin>>i;
    /*for(auto &i:mp){
        for(auto &c:i){
            c=(c=='.'?'0':'1');
        }
    }*/
    vector<vector<vector<int>>> dis(n,vector<vector<int>>(m,vector<int>(2,1e9)));
    queue<tuple<int,int,int>> q;
    if(mp[0][0]=='.'){
        q.push({0,0,0});
        dis[0][0][0]=0;
    }
    if(mp[0][0]=='S'){
        q.push({0,0,1});
        dis[0][0][1]=0;
        q.push({0,0,0});
        dis[0][0][0]=0;
    }
    /*if(mp[0][0]=='#'){
        q.push({0,0,1});
        dis[0][0][1]=0;
    }*/
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    #define check(a,b) (((a)<n) and ((a)>=0) and ((b)<m) and ((b)>=0))
    while(!q.empty()){
        auto [x,y,p]=q.front();q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(!(check(nx,ny))) continue;
            int nxtp=p;
            if(mp[nx][ny]=='S' or mp[nx][ny]=='s'){
                nxtp=p^1;
            }
            /*if(dis[nx][ny][nxtp]!=1e9){
                continue;
            }*/
            if(mp[nx][ny]=='S' or mp[nx][ny]=='s'){
                if (dis[x][y][p]+1<dis[nx][ny][nxtp]){
                    dis[nx][ny][nxtp]=dis[nx][ny][p]=dis[x][y][p]+1;
                    q.push({nx,ny,nxtp});
                    q.push({nx,ny,p});
                }
            }
            else{
                if(p==0){
                    if(mp[nx][ny]=='.'){
                        if (dis[x][y][p]+1<dis[nx][ny][nxtp]){
                        dis[nx][ny][nxtp]=dis[x][y][p]+1;
                        q.push({nx,ny,nxtp});
                }
                    }
                }
                else{
                    if(mp[nx][ny]=='#'){
                        if (dis[x][y][p]+1<dis[nx][ny][nxtp]){
                        dis[nx][ny][nxtp]=dis[x][y][p]+1;
                        q.push({nx,ny,nxtp});
                        }
                    }
                }
            }
        }
    }
    int ans=1e9;
    ans=min(dis[n-1][m-1][0],dis[n-1][m-1][1]);
    cout<<(ans==1e9?-1:ans);







}