P1026 逃跑的拉爾夫

時(shí)間限制: 1 s
空間限制: 128000 KB
題目等級 : 黃金 Gold

題目描述 Decription

年輕的拉爾夫開玩笑地從一個小鎮(zhèn)上偷走了一輛車，但他沒想到的是那輛車屬于警察局嘱丢，并且車上裝有用于發(fā)射車子移動路線的裝置泡挺。
那個裝置太舊了，以至于只能發(fā)射關(guān)于那輛車的移動路線的方向信息熟菲。
編寫程序，通過使用一張小鎮(zhèn)的地圖幫助警察局找到那輛車椭更。程序必須能表示出該車最終所有可能的位置铣揉。
小鎮(zhèn)的地圖是矩形的饶深，上面的符號用來標(biāo)明哪兒可以行車哪兒不行」涔埃“.”表示小鎮(zhèn)上那塊地方是可以行車的敌厘，而符號“X”表示此處不能行車。拉爾夫所開小車的初始位置用字符的“*”表示朽合，且汽車能從初始位置通過俱两。
汽車能向四個方向移動：向北(向上)，向南(向下)曹步，向西(向左)宪彩，向東(向右)。
拉爾夫所開小車的行動路線是通過一組給定的方向來描述的讲婚。在每個給定的方向尿孔，拉爾夫駕駛小車通過小鎮(zhèn)上一個或更多的可行車地點(diǎn)。

輸入描述 Input Description

輸入文件的第一行包含兩個用空格隔開的自然數(shù)R和C筹麸，1≤R≤50活合，1≤C≤50，分別表示小鎮(zhèn)地圖中的行數(shù)和列數(shù)物赶。
以下的R行中每行都包含一組C個符號(“.”或“X”或“*”)用來描述地圖上相應(yīng)的部位芜辕。
接下來的第R+2行包含一個自然數(shù)N，1≤N≤1000块差，表示一組方向的長度侵续。
接下來的N行幅行包含下述單詞中的任一個：NORTH(北)、SOUTH(南)憨闰、WEST(西)和EAST(東)状蜗，表示汽車移動的方向，任何兩個連續(xù)的方向都不相同鹉动。

輸出描述 Output Description

輸出文件應(yīng)包含用R行表示的小鎮(zhèn)的地圖(象輸入文件中一樣)轧坎，字符“*”應(yīng)該僅用來表示汽車最終可能出現(xiàn)的位置。

樣例輸入 Sample Input

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

樣例輸出 Sample Output

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

數(shù)據(jù)范圍及提示 Data Size & Hint

NULL

題解

不需要用BFS泽示，這里解釋DFS做法：
用一個f[i][j][k]數(shù)組表示在(i,j)位置第k個指令的訪問狀態(tài)缸血，都初始化成未訪問狀態(tài)，然后走一步把一個位置更新為訪問狀態(tài)

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記錄可到達(dá)的點(diǎn)
//f[i][j][k]記錄(i,j)點(diǎn)第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;
}