使用 dfs,代码如下：

#include <iostream>
using namespace std;


int n,m,c;
char G[510][510],sx,sy,flag[510][510][2020];
int opt[5500],dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};

void dfs(int step,int cx,int cy)
{
    if (flag[cx][cy][step]==1)return;
    flag[cx][cy][step]=1;
	if (G[cx][cy]=='X')return;
	if (step==c)
	{
		G[cx][cy]='*';
		return;
	}
	
	while (!(cx<1||cx>m||cy<1||cy>n))
	{
		if (G[cx][cy]=='X')break;
		cy+=dx[opt[step+1]];
		cx+=dy[opt[step+1]];
		dfs(step+1,cx,cy);
	}
}

int main()
{
	cin >> n >> m;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			cin >> G[i][j];
			if (G[i][j]=='*')
			{
				sx=i;
				sy=j;
			}
		}
	}
	cin >> c;
	for (int i=1;i<=c;i++)
	{
		string temp;
		cin >> temp;
		if (temp=="NORTH")opt[i]=0;
		if (temp=="SOUTH")opt[i]=1;
		if (temp=="EAST")opt[i]=2;
		if (temp=="WEST")opt[i]=3;
		//cout << opt[i] << endl;
	}
	G[sx][sy]='.';
	dfs(0,sx,sy);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			cout << G[i][j];
		}
		cout << endl;
	}	
	return 0;
}

AC 必关！