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; }