题解 P1189 【SEARCH】
MorsLin
2018-04-01 16:17:27
*先反省一波:我以后再也不用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/)