//this is C++ file. Not a C file.
//potion=1,minion=2,Deathtouch=3,exit=4,seal=5;
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

struct node {
int x,y,dir;
};

class Stack {
struct node *st;
int top;
int size;
public:
Stack();
~Stack() {free(st);}
int Isfull() {return(top==size-1);}
int Isempty() {return(top==-1);}
void push(struct node mynode) {st[++top]=mynode;}
struct node pop() {return(st[top--]);}
void Resize() {size*=2; st=(struct node *)realloc(st,size*sizeof(struct node));}
};

class Matris
{
public:
	unsigned char mat[41][41];
	int father;
	int coordx,coordy;
	int sealsbroken,deathtouch,potion;
	int depth;
	void Initialize();
	void Read_Input(char argv[]);
	int Available(int x,int y);
	void Solve();
	friend void Make_Child(class Matris *matarray);
	friend int Matmatch(class Matris &ilk,class Matris &son);
	friend int Yol_var(class Matris &ilk,int k,int l);
};

class Matris matarray[1000];
int rowsize,columnsize;
int path[100];

Stack::Stack()
{
	st=(struct node *)malloc(100*sizeof(struct node));
	top=-1;
	size=100;
}

int Matris::Available(int x,int y)
{
return(x<rowsize && y<columnsize && mat[x][y]!='=' && x>-1 && y>-1
   && mat[x][y]!='M' && mat[x][y]!='S' && mat[x][y]!='E');
}

void Matris::Solve()
{
 struct node temp;
 temp.x=coordx;
 temp.y=coordy;
 temp.dir=0;
 class Stack mystack;
 for(;;)
 {
 switch(temp.dir){
 case 0 : if(Available(temp.x,temp.y-1))
	  {
	  temp.dir++;
	  if(mystack.Isfull())
	   mystack.Resize();
	  mystack.push(temp);
	  temp.y--;
	  temp.dir=0;
	  if(mat[temp.x][temp.y]=='P')
		  mat[temp.x][temp.y]=128;
	  if(mat[temp.x][temp.y]=='D')
		  mat[temp.x][temp.y]=129;
	  if(mat[temp.x][temp.y]=='E')
		  mat[temp.x][temp.y]=130;
	  mat[temp.x][temp.y]+=1;
	  } else
	  {
	   temp.dir++;
	   continue;
	  }
	  break;
 case 1 : if(Available(temp.x-1,temp.y))
	  {
	  temp.dir++;
	  if(mystack.Isfull())
	   mystack.Resize();
	  mystack.push(temp);
	  temp.x--;
	  temp.dir=0;
	  if(mat[temp.x][temp.y]=='P')
		  mat[temp.x][temp.y]=128;
	  if(mat[temp.x][temp.y]=='D')
		  mat[temp.x][temp.y]=129;
	  if(mat[temp.x][temp.y]=='E')
		  mat[temp.x][temp.y]=130;
	  mat[temp.x][temp.y]+=1;
	  } else
	  {
	   temp.dir++;
	   continue;
	  }
	  break;
 case 2 : if(Available(temp.x,temp.y+1))
	  {
	  temp.dir++;
	  if(mystack.Isfull())
	   mystack.Resize();
	  mystack.push(temp);
	  temp.y++;
	  temp.dir=0;
	  if(mat[temp.x][temp.y]=='P')
		  mat[temp.x][temp.y]=128;
	  if(mat[temp.x][temp.y]=='D')
		  mat[temp.x][temp.y]=129;
	  if(mat[temp.x][temp.y]=='E')
		  mat[temp.x][temp.y]=130;
	  mat[temp.x][temp.y]+=1;
	  } else
	  {
	   temp.dir++;
	   continue;
	  }
	  break;
 case 3 : if(Available(temp.x+1,temp.y))
	  {
	  temp.dir++;
	  if(mystack.Isfull())
	   mystack.Resize();
	  mystack.push(temp);
	  temp.x++;
	  temp.dir=0;
	  if(mat[temp.x][temp.y]=='P')
		  mat[temp.x][temp.y]=128;
	  if(mat[temp.x][temp.y]=='D')
		  mat[temp.x][temp.y]=129;
	  if(mat[temp.x][temp.y]=='E')
		  mat[temp.x][temp.y]=130;
	  mat[temp.x][temp.y]+=1;
	  } else
	  {
	   temp.dir++;
	   continue;
	  }
	  break;
 default: if(mystack.Isempty())
	     goto JUMPINGPOINT;
	    else
	      temp=mystack.pop();
	    break;
 }
 }
JUMPINGPOINT:;
}

void Matris::Initialize()
{
  sealsbroken=deathtouch=potion=0;
  coordx=coordy=0;
  father=-1;
}

void Matris::Read_Input(char argv[])
{
	FILE *f;
	int i;
	f=fopen(argv,"r");
	fscanf(f,"%d%d",&rowsize,&columnsize);
	fgetc(f);
	for(i=0;i<rowsize;i++)
	{
	fgets((char *)mat[i],columnsize+1,f);
	fgetc(f);
	}
	fclose(f);
}


int Matmatch(class Matris &ilk,class Matris &son)
{
	int i,j;
	for(i=0;i<rowsize;i++)
		for(j=0;j<columnsize;j++)
			if(ilk.mat[i][j]!=son.mat[i][j])
				return(0);
			if(ilk.potion!=son.potion) return(0);
			if(ilk.deathtouch!=son.deathtouch) return(0);
			if(ilk.coordx!=son.coordx || ilk.coordy!=son.coordy) return(0);
			if(ilk.sealsbroken!=son.sealsbroken) return(0);
			return(1);
}

int Yol_var(class Matris &ilk,int k,int l)
{
	if((k!=0&&ilk.mat[k-1][l]==' ') ||(l!=0&&ilk.mat[k][l-1]==' ')
		||(k<rowsize-1 && ilk.mat[k+1][l]==' ')||(l<columnsize-1 && ilk.mat[k][l+1]==' '))
		return(0);
	return(1);
}

void Make_Child()
{
	int i,j,k,l;
	int matarbas=0,matarson=1;
	for(;;matarbas++)
	{
	matarray[matarbas].Solve();
	for(i=0;i<rowsize;i++)
		for(j=0;j<columnsize;j++)
		switch(matarray[k].mat[i][j]){
		case 129 : if(!matarray[matarbas].potion && !matarray[matarbas].deathtouch)
				   {
					   for(k=0;k<rowsize;k++)
						   for(l=0;l<columnsize;l++)
							   if(matarray[matarbas].mat[k][l]!=128)
								   matarray[matarson].mat[k][l]=matarray[matarbas].mat[k][l];
						   matarray[matarson].father=matarbas;
						   matarray[matarson].potion=1;
						   matarray[matarson].deathtouch=0;
						   matarray[matarson].coordx=i;
						   matarray[matarson].coordy=j;
						   matarray[matarson].mat[i][j]=' ';
						   matarray[matarson].sealsbroken=matarray[matarbas].sealsbroken;
						   matarray[matarson].depth=matarray[matarbas].depth+1;
						   for(k=0;k<matarson;k++)
							   if(matarray[k].depth==matarray[matarson].depth && !Matmatch(matarray[k],matarray[matarson]))
								   matarson++;
				   } break;
		case 'M' : if(Yol_var(matarray[matarbas],i,j) && matarray[matarbas].potion)
				   {
					   for(k=0;k<rowsize;k++)
						   for(l=0;l<columnsize;l++)
							   if(matarray[matarbas].mat[k][l]<128)
								   matarray[matarson].mat[k][l]=matarray[matarbas].mat[k][l];
						   matarray[matarson].father=matarbas;
						   matarray[matarson].potion=0;
						   matarray[matarson].deathtouch=0;
						   matarray[matarson].coordx=i;
						   matarray[matarson].coordy=j;
						   matarray[matarson].mat[i][j]=' ';
						   matarray[matarson].sealsbroken=matarray[matarbas].sealsbroken;
						   matarray[matarson].depth=matarray[matarbas].depth+1;
						   for(k=0;k<matarson;k++)
							   if(matarray[k].depth==matarray[matarson].depth && !Matmatch(matarray[k],matarray[matarson]))
								   matarson++;							   
				   } break;
		case 'S' : if(Yol_var(matarray[matarbas],i,j))
				   {
					   for(k=0;k<rowsize;k++)
						   for(l=0;l<columnsize;l++)
							   if(matarray[matarbas].mat[k][l]<128)
								   matarray[matarson].mat[k][l]=matarray[matarbas].mat[k][l];
						   matarray[matarson].potion=matarray[matarbas].potion;
						   matarray[matarson].deathtouch=matarray[matarbas].deathtouch;
						   matarray[matarson].father=matarbas;
						   matarray[matarson].coordx=i;
						   matarray[matarson].coordy=j;
						   matarray[matarson].mat[i][j]=' ';
						   matarray[matarson].sealsbroken=matarray[matarbas].sealsbroken+1;
						   matarray[matarson].depth=matarray[matarbas].depth+1;
						   for(k=0;k<matarson;k++)
							   if(matarray[k].depth==matarray[matarson].depth && !Matmatch(matarray[k],matarray[matarson]))
								   matarson++;							   
				   } break;
		case 130 : if(!matarray[matarbas].potion && matarray[matarbas].sealsbroken==4 && Yol_var(matarray[matarbas],i,j))
				   {
					   for(k=0;k<rowsize;k++)
						   for(l=0;l<columnsize;l++)
							   if(matarray[matarbas].mat[k][l]!=128)
								   matarray[matarson].mat[k][l]=matarray[matarbas].mat[k][l];
						   matarray[matarson].potion=matarray[matarbas].potion;
						   matarray[matarson].deathtouch=matarray[matarbas].deathtouch;
						   matarray[matarson].father=matarbas;
						   matarray[matarson].coordx=i;
						   matarray[matarson].coordy=j;
						   matarray[matarson].mat[i][j]=' ';
						   matarray[matarson].sealsbroken=matarray[matarbas].sealsbroken+1;
						   matarray[matarson].depth=matarray[matarbas].depth+1;
						   for(k=0;k<matarson;k++)
							   if(matarray[k].depth==matarray[matarson].depth && !Matmatch(matarray[k],matarray[matarson]))
								   matarson++;							   
				   } break;
		case 131 : if(matarray[matarbas].sealsbroken==4 && matarray[matarbas].deathtouch && Yol_var(matarray[matarbas],i,j))
				   {for(k=0;k<rowsize;k++)
						   for(l=0;l<columnsize;l++)
							   if(matarray[matarbas].mat[k][l]!=128)
								   matarray[matarson].mat[k][l]=matarray[matarbas].mat[k][l];
						   matarray[matarson].father=matarbas;
						   matarray[matarson].coordx=i;
						   matarray[matarson].coordy=j;
						   matarray[matarson].mat[i][j]=' ';
						   goto JUMPING;
				   } break;
		default : break;
	}
       }
JUMPING:
	for(k=0;matarray[matarson].father!=-1;k++)
	{
		path[k]=matarson;
		matarson=matarray[matarson].father;
	}
	path[k]=0;
//burda kaldin	
}

int main(int argc,char *argv[])
{
	matarray[0].Initialize();
	matarray[0].Read_Input(argv[1]);
	Make_Child();
	return 0;
}