【codevs1026】逃跑的拉尔夫

problem

solution

codes

#include<cstdio>
#include<queue>
#include<set>//set判重防MLE
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int r, c, c1, r1, n, go[1010];
char a[55][55];
struct node{ 
    int x, y, step; 
    node(int x, int y, int step):x(x),y(y),step(step){}
};
queue<node>q;
set<int>s;

bool inside(int x, int y){ return (x<r && x>=0 && y<c && y>=0 && a[x][y]!='X'); }

int togo(char ch){
    if(ch == 'N')return 0;
    if(ch == 'E')return 1;
    if(ch == 'S')return 2;
    if(ch == 'W')return 3;
}

void bfs(){
    q.push(node(r1, c1, 0));
    while(q.size()){
        node t = q.front();  q.pop();
        if(t.step == n)a[t.x][t.y] = '*';
        int tt=go[t.step], nx=t.x+dx[tt], ny=t.y+dy[tt];
        while(inside(nx,ny)){
            int ok = nx*1000000+ny*10000+t.step+1;
            if(!s.count(ok)){
                q.push(node(nx,ny,t.step+1));
                s.insert(ok);
            }
            nx += dx[tt], ny += dy[tt];
        }
    }
    return ;
}

int main(){
    scanf("%d%d", &r, &c);
    for(int i = 0; i < r; i++)scanf("%s", a[i]);
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            if(a[i][j] == '*'){ r1 = i; c1 = j; break;}
    a[r1][c1] = '.';
    scanf("%d",&n);
    for(int i= 0; i < n; i++){
        char t[10];  scanf("%s", t);  go[i] = togo(t[0]);
    }
    bfs();
    for(int i = 0; i < r; i++)printf("%s\n", a[i]);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80516468