#include<bits/stdc++.h> using namespace std; int n,m,k,l,fy[4]={1,0,-1,0},po,fx[4]={0,1,0,-1}; char a[600][600]; int u,q=-1,w=INT_MAX,e,ans=0; void asd(int x,int y){ ans++; if(a[x][y]=='E'){ if(w>ans){ w=ans; } ans--; return; } for(int i=0;i<4;i++){ int tx=fx[i]+x; int ty=fy[i]+y; if(tx>0&&ty>0&&tx<=n&&ty<=m&&(a[tx][ty]=='.'||a[tx][ty]=='S'||a[tx][ty]=='E')){ a[x][y]='#'; asd(tx,ty); if(x==k&&y==l){ a[x][y]='S'; } a[x][y]='.'; } } ans--; return; } int main(){ cin>>n>>m>>po; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='S'){ k=i; l=j; } } } asd(k,l); if(w>10000000){ cout<<-1; }else{ cout<<(w-1)*po; } } /************************************************************** Problem: 2109 User: zhengzihao Language: C++ Result: Time Limit Exceed ****************************************************************/