```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
char mp[55][55];
struct f
{
int fx,fy;
} fang_mp[5];
int fang_n;
bool dp_mp[60][60][1005];
char fang[1005];
short int fang_sum_H(char s)
{
if(s=='N')
return 1;
if(s=='S')
return 2;
if(s=='W')
return 3;
if(s=='E')
return 4;
}
void dfs(int x,int y,int step)
{
if(step==fang_n)
{
mp[x][y]='*';
return;
}
if(dp_mp[x][y][step])
return;
else
dp_mp[x][y][step]=true;
int xx=x;
int yy=y;
step++;
short int k=fang_sum_H(fang[step]);
while(1)
{
xx+=fang_mp[k].fx;
yy+=fang_mp[k].fy;
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]!='X')
dfs(xx,yy,step);
else
break;
}
return;
}
int main()
{
string s;
cin>>n>>m;
int x,y;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
mp[i][j+1]=s[j];
if(mp[i][j+1]=='*')
{
x=i;
y=j+1;
mp[i][j+1]='.';
}
}
}
cin>>fang_n;
for(int i=1;i<=fang_n;i++)
{
string fang_;
cin>>fang_;
fang[i]=fang_[0];
// fang_sum_H(fang);
}
/* for(int i=1;i<=4;i++)
cout<<fang_sum[i]<<endl;*/
fang_mp[1].fx=-1,fang_mp[1].fy=0;
fang_mp[2].fx=1,fang_mp[2].fy=0;
fang_mp[3].fy=-1,fang_mp[3].fx=0;
fang_mp[4].fy=1,fang_mp[4].fx=0;
dfs(x,y,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<mp[i][j];
cout<<endl;
}
return 0;
}
//dfs
by Sword_wielder @ 2022-10-19 11:21:14