【题解】　逃跑的拉尔夫　搜索

传送门＝￣ω￣＝

思路：深搜函数dfs(h,w,d)表示当前正在第h行，第w列，目前正在执行第d个操作，如果d>n 说明现在没有操作可以做了，于是当前的坐标 (h,w) 为一个可能的最终位置。

代码：

#include <bits/stdc++.h>
using namespace std;
int r,c,n,ctrl[1005],sh,sw;
char mp[55][55];
bool book[55][55][1005];
string s;
void dfs(int h,int w,int d)
{
    if(book[h][w][d])return;
    if(d>n){mp[h][w]='*';return;}
    book[h][w][d]=1;
    for(int i=1;;i++)
    {
        if(ctrl[d]==1)
        {
            if(h-i<1||mp[h-i][w]=='X')break;
            dfs(h-i,w,d+1);
        }
        else if(ctrl[d]==2)
        {
            if(h+i>r||mp[h+i][w]=='X')break;
            dfs(h+i,w,d+1);
        }
        else if(ctrl[d]==3)
        {
            if(w-i<1||mp[h][w-i]=='X')break;
            dfs(h,w-i,d+1);
        }
        else if(ctrl[d]==4)
        {
            if(w+i>c||mp[h][w+i]=='X')break;
            dfs(h,w+i,d+1);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            cin>>mp[i][j];if(mp[i][j]=='*')sh=i,sw=j,mp[i][j]='.';
        }
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s,ctrl[i]=s=="NORTH"?1:s=="SOUTH"?2:s=="WEST"?3:4;
    dfs(sh,sw,1);
    for(int i=1;i<=r;i++,cout<<endl)for(int j=1;j<=c;j++)cout<<mp[i][j];
    return 0;
}