#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int Size = 1000;
struct Node
{
int x, y, count;
};
char map[ Size ][ Size ];
int m, n, x1, y1, x2, y2, pi[ Size * Size ], min_count;
bool visit[ Size ][ Size ];
queue<Node> q;
void init( )
{
int i, j;
Node p;
cin >> m >> n;
for ( i = 0; i < m; i++ )
cin >> map[ i ];
for ( i = 0; i < m; i++ )
for ( j = 0; j < n; j++ )
{
pi[ i * n + j ] = -1;
visit[ i ][ j ] = false;
if ( map[ i ][ j ] == 'S' )
{
x1 = i;
y1 = j;
}
if ( map [ i ][ j ] == 'E' )
{
x2 = i;
y2 = j;
}
}
p.x = x1;
p.y = y1;
p.count = 0;
q.push( p );
visit[ x1 ][ y1 ] = true;
min_count = 0;
}
void setNode( Node p, int x, int y )
{
if ( x < 0 || x >= m || y < 0 || y >= n )
return ;
if ( visit[ x ][ y ] || map[ x ][ y ] == '#' )
return ;
visit[ x ][ y ] = true;
pi[ x * n + y ] = p.x * n + p.y;
p.x = x;
p.y = y;
p.count++;
q.push( p );
}
void work( )
{
Node p;
while ( !q.empty( ) )
{
p = q.front( );
q.pop( );
if ( p.x == x2 && p.y == y2 )
{
min_count = p.count;
break;
}
setNode( p, p.x - 1, p.y );
setNode( p, p.x + 1, p.y );
setNode( p, p.x, p.y - 1 );
setNode( p, p.x, p.y + 1 );
}
}
void print( )
{
if ( min_count )
{
cout << "Min Count = " << min_count << endl;
stack<int> s;
s.push( x2 * n + y2 );
while ( pi[ s.top( ) ] != -1 )
s.push( pi[ s.top( ) ] );
cout << "(" << x1 << ", " << y1 << ")";
s.pop( );
while ( !s.empty( ) )
{
cout << " -> (" << s.top( ) / n << ", " << s.top( ) % n << ")";
s.pop( );
}
cout << endl;
}
else
cout << "None!" << endl;
}
int main( )
{
init( );
work( );
print( );
return 0;
}
