题目描述

年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。

那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。

编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。

小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的，而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。

汽车能向四个方向移动：向北(向上)，向南(向下)，向西(向左)，向东(向右)。

拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

思路

bfs每一走的位置，记录一个step表示当前为第几个方向
开一个f[x][y][step]的数组表示第step步时(x,y)这个点有没有被走过
然后就可以了

#include 
#include 
#include 
#include 
#define maxn 51
#define maxk 1001
using namespace std;
struct edge
{
    int x,y,step;
};
queue t;
int n,m,r,sx,sy;
int dis[maxk],a[maxn][maxn],f[maxn][maxn][maxk];
int bfs()
{
    edge l;
    l.x=sx; l.y=sy; l.step=1;
    t.push(l);
    while (!t.empty())
    {
        edge now=t.front();
        t.pop();
        if (now.step==r+1) 
        {
            a[now.x][now.y]=-1;
        }
        int dx,dy,chp=now.step;
        if (dis[chp]==1) dx=-1,dy=0;
        if (dis[chp]==2) dx=1,dy=0;
        if (dis[chp]==3) dx=0,dy=-1;
        if (dis[chp]==4) dx=0,dy=1;
        int xx=now.x,yy=now.y;
        while (xx+dx>=1&&xx+dx<=n&&yy+dy>=1&&yy+dy<=m&&a[xx+dx][yy+dy]==0&&f[xx+dx][yy+dy][now.step+1]==0&&now.step<=r)
        {
            edge zhx;
            zhx.x=xx+dx;
            zhx.y=yy+dy;
            zhx.step=now.step+1;
            t.push(zhx);
            f[xx+dx][yy+dy][now.step+1]=1;
            xx+=dx; yy+=dy;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        char ch[maxn];
        cin>>ch;
        for (int j=1;j<=m;j++)
        {
            if (ch[j-1]=='X')
                a[i][j]=1;
            if (ch[j-1]=='*')
            {
                sx=i;
                sy=j;
            }   
        }
    }
    scanf("%d",&r);
    for (int i=1;i<=r;i++)
    {
        char ch[maxn];
        cin>>ch;
        if (ch[0]=='N') dis[i]=1;
        if (ch[0]=='S') dis[i]=2;
        if (ch[0]=='W') dis[i]=3;
        if (ch[0]=='E') dis[i]=4;
    }

    bfs();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (a[i][j]==1) printf("X");
            else if (a[i][j]==-1) printf("*");
            else printf(".");
        }
        printf("\n");
    }
}