美文网首页
题解 Code[vs] P1026 逃跑的拉尔夫

题解 Code[vs] P1026 逃跑的拉尔夫

作者: Ricardo_Y_Li | 来源:发表于2017-07-06 16:11 被阅读0次

    P1026 逃跑的拉尔夫


    时间限制: 1 s
    空间限制: 128000 KB
    题目等级 : 黄金 Gold


    题目描述 Decription

    年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车,但他没想到的是那辆车属于警察局,并且车上装有用于发射车子移动路线的装置。
    那个装置太旧了,以至于只能发射关于那辆车的移动路线的方向信息。
    编写程序,通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。
    小镇的地图是矩形的,上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的,而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示,且汽车能从初始位置通过。
    汽车能向四个方向移动:向北(向上),向南(向下),向西(向左),向东(向右)。
    拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向,拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

    输入描述 Input Description

    输入文件的第一行包含两个用空格隔开的自然数R和C,1≤R≤50,1≤C≤50,分别表示小镇地图中的行数和列数。
    以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位。
    接下来的第R+2行包含一个自然数N,1≤N≤1000,表示一组方向的长度。
    接下来的N行幅行包含下述单词中的任一个:NORTH(北)、SOUTH(南)、WEST(西)和EAST(东),表示汽车移动的方向,任何两个连续的方向都不相同。

    输出描述 Output Description

    输出文件应包含用R行表示的小镇的地图(象输入文件中一样),字符“*”应该仅用来表示汽车最终可能出现的位置。

    样例输入 Sample Input

    4 5
    .....
    .X...
    ...*X
    X.X..
    3
    NORTH
    WEST
    SOUTH

    样例输出 Sample Output

    .....
    *****X*****..
    **..X
    X.X..

    数据范围及提示 Data Size & Hint

    NULL

    题解

    不需要用BFS,这里解释DFS做法:
    用一个f[i][j][k]数组表示在(i,j)位置第k个指令的访问状态,都初始化成未访问状态,然后走一步把一个位置更新为访问状态

    C++代码

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int m,n,k,a,b,x,y;
    int map[51][51],ord[1010],vis[51][51],f[51][51][1010];
    //map记录地图,ord记录指令,vis记录可到达的点
    //f[i][j][k]记录(i,j)点第k个指令 
    
    void print(){
        for(int i=1;i<=a;i++){
            for(int j=1;j<=b;j++){
                if(vis[i][j]){
                    cout<<"*";
                    continue;
                }
                if(map[i][j])cout<<".";
                if(!map[i][j])cout<<"X";
            }
            cout<<endl;
        }
    }
    
    void dfs(int x,int y,int cnt){
        if(cnt==n){
            vis[x][y]=1;
            return;
        }
        if(f[x][y][cnt]!=0)
            return;
        f[x][y][cnt]=1;
        if(ord[cnt]==1){
            while((x-1>=1) && (map[x-1][y])){  
                x--;  
                dfs(x,y,cnt+1);  
            }  
        }
        if(ord[cnt]==2){
            while((x+1<=a) && (map[x+1][y])){
                x++;
                dfs(x,y,cnt+1);
            }
        }
        if(ord[cnt]==3){
            while((y+1<=b) && (map[x][y+1])){
                y++;
                dfs(x,y,cnt+1);
            }
        }
        if(ord[cnt]==4){
            while((y-1>=1) && (map[x][y-1])){
                y--;
                dfs(x,y,cnt+1);
            }
        }
    }
    
    int main(){
        ios::sync_with_stdio(0);
        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
        cin>>a>>b;
        for(int i=1;i<=a;i++)
            for(int j=1;j<=b;j++){
                char c;
                cin>>c;
                if(c=='.')map[i][j]=1;
                if(c=='X')map[i][j]=0;
                if(c=='*'){
                    x=i;
                    y=j;
                    map[i][j]=1;
                }
            }
        cin>>n;
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            if(s[0]=='N')ord[i]=1;
            if(s[0]=='S')ord[i]=2;
            if(s[0]=='E')ord[i]=3;
            if(s[0]=='W')ord[i]=4;
        }
        dfs(x,y,0);
        print();
        return 0;
    } 
    

    相关文章

      网友评论

          本文标题:题解 Code[vs] P1026 逃跑的拉尔夫

          本文链接:https://www.haomeiwen.com/subject/byghhxtx.html