dungeons

#include <bits/stdc++.h>

using namespace std;
const int N = 405;
int vizibil[N][N],pericol[N][N],x[64],y[64],sol=N*N,coins(int64_t);
int di[8]= {-1,0,1,0,1,-1,-1,1};
int dj[8]= {0,1,0,-1,1,-1,1,-1};
char Map[N][N];
int n,m,k;
int64_t P[64];
unordered_map<int64_t,int> invP;
void readData(),solve(),getS(int64_t,vector<int>&);
queue<int64_t> q;
bitset<N> vizit[N];
int main()
{
    readData();
    solve();
    return 0;
}
void readData()
{
    cin>>n>>m;
    k=0;
    P[0]=1;
    invP[P[0]]=0;
    /// mapez S-urile cu puteri de 2
    for(int i=0; i<n; i++)
    {
        cin>>Map[i];
        for(int j=0; j<m; j++)
            if(Map[i][j]=='S')
            {
                Map[i][j]='.';
                x[k]=i;
                y[k]=j;
                k++;
                P[k]=2LL*P[k-1];
                invP[P[k]]=k;
            }
    }
    assert(k<=60);
    /// creez harta vizibilitatilor
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
                for(int d=0,p3=1; d<8; d++,p3*=3)
                {
                    int I=i+di[d];
                    int J=j+dj[d];
                    if(Map[I][J]=='o')
                        vizibil[i][j]+=p3;
                    else
                    if(Map[I][J]=='#')
                        vizibil[i][j]+=2*p3;
                }
}

void solve()
{
    q.push((1LL<<k)-1LL);
    for(; q.size(); q.pop())
        sol=min(sol,coins(q.front()));
    cout<<sol;
}
int coins(int64_t MASK)
{
    int _coins=0;
    for(int i=0; i<n; i++)
        vizit[i].reset();
    vector<int> id;
    vector<int> sx;
    vector<int> sy;
    vector<int64_t> p2;
    for(;MASK;MASK-=MASK&(-MASK))
        p2.push_back(MASK&(-MASK));
    for(auto it:p2)
        id.push_back(invP[it]);
    for(auto it:id)
    {
        sx.push_back(x[it]);
        sy.push_back(y[it]);
    }
    int nr=id.size();
    /// setam deplasamentele pentru toate cele
    queue<int> qx,qy;
    qx.push(sx[0]);
    qy.push(sy[0]);
    vizit[sx[0]][sy[0]]=1;
    while(qx.size())
    {
        int X=qx.front();qx.pop();
        int Y=qy.front();qy.pop();
        int vizA = vizibil[X][Y];
        int64_t codA=0,codB=0;
        for(int i=0;i<nr;i++)
            if(vizibil[X+sx[i]-sx[0]][Y+sy[i]-sy[0]]==vizA)
                codA|=p2[i];
            else
                codB|=p2[i];
        if(codB)
        {
            q.push(codA);
            q.push(codB);
            return N*N;
        }
        for(int d=0;d<4;d++)
        {
            int I=X+di[d];
            int J=Y+dj[d];
            if(vizit[I][J])
                continue;
            vizit[I][J]=1;
            char ch=Map[I][J];
            if(ch=='.')
                for(int i=0;i<nr;i++)
                if(Map[I+sx[i]-sx[0]][J+sy[i]-sy[0]]=='X')
                {
                    ch='X';
                    break;
                }
            if(ch=='#'||ch=='X')
                continue;
            qx.push(I);
            qy.push(J);
            if(ch=='o')
                _coins++;
        }
    }
    return _coins;
}