题解 P1189 【SEARCH】

*先反省一波：我以后再也不用getchar()+scanf了(日常爆零)* - 算是比较裸的搜索吧，在下用的算是DFS(严格说来应该是枚举)+在线处理吧，就是一边输入方向一边处理，用ans数组表示输入这一次方向后汽车可能在的位置，每次输入方向后将不能继续前进的ans删去，将可以前进的ans更新到新的位置 ```cpp void dfs(int x,int y,int dir,int l) { if(map[x+fx[dir]][y+fy[dir]]) //如果不能继续前进，那么这个ans一定是错的，将它删去 { ans[x][y]=0; return ; } for(int i=1;;i++) //知道我为什么说它是枚举了吧 qwq { int xx=x+fx[dir]*i,yy=y+fy[dir]*i; if(xx<1||xx>n||yy<1||yy>m||map[xx][yy]) //不断前进，并将这条路全置为ans(因为都符合条件) break; ans[xx][yy]=l+1; //防止重复查找，即防止刚置为ans后没有进行下一重循环，直接在这层循环再搜一次 } return ; } ``` - 上面的dfs函数可以去掉不能继续前进的答案，加入新的答案，那么旧的答案该怎么办呢？ 我们可以在循环到ans后直接将它删去，因为对我们来说它已经没用了。接下来直接上代码 ```cpp #include<iostream> #include<cstdio> using namespace std; bool map[51][51]; //判断有没有障碍物 int ans[51][51]; //存答案 char mmp[51][51]; //存地图，不要在意变量名 int n,m,k; int fx[5]={0,0,0,1,-1}; //存方向，顺序是E、W、S、N int fy[5]={0,1,-1,0,0}; void dfs(int x,int y,int dir,int l) { if(map[x+fx[dir]][y+fy[dir]]) //如果不能继续前进，那么这个ans一定是错的，将它删去 { ans[x][y]=0; return ; } for(int i=1;;i++) //知道我为什么说它是枚举了吧 qwq { int xx=x+fx[dir]*i,yy=y+fy[dir]*i; if(xx<1||xx>n||yy<1||yy>m||map[xx][yy]) //不断前进，并将这条路全置为ans(因为都符合条件) break; ans[xx][yy]=l+1; //防止重复查找，即刚置为ans后没有进行下一重循环，直接在这层循环再搜一次 } return ; } int main() { 输入+预处理地图 scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>mmp[i][j]; if(mmp[i][j]=='X') map[i][j]=1; if(mmp[i][j]=='*') ans[i][j]=1; } } //在线查找 scanf("%d",&k); for(int o=1;o<=k;o++) { char a[10]; scanf("%s",a); if(a[0]=='E') { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(ans[i][j]==o) { ans[i][j]=0; //将旧的答案删去，下同 dfs(i,j,1,o); //用当层的答案去寻找新的答案 } } } if(a[0]=='W') { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(ans[i][j]==o) { ans[i][j]=0; dfs(i,j,2,o); } } } if(a[0]=='S') { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(ans[i][j]==o) { ans[i][j]=0; dfs(i,j,3,o); } } } if(a[0]=='N') { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(ans[i][j]==o) { ans[i][j]=0; dfs(i,j,4,o); } } } } //输出 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!ans[i][j]&&mmp[i][j]=='*'){cout<<'.'; continue;} if(!ans[i][j]) cout<<mmp[i][j]; else cout<<'*'; } cout<<endl; } return 0; } ``` - 广告时间 在下的[洛谷博客](https://www.luogu.org/blog/34188/)和[博客园](http://www.cnblogs.com/wxl-Ezio/)