题解 P1189 【SEARCH】

MorsLin · 2018-04-01 16:17:27 · 题解

先反省一波：我以后再也不用getchar()+scanf了(日常爆零)

• 算是比较裸的搜索吧，在下用的算是DFS(严格说来应该是枚举)+在线处理吧，就是一边输入方向一边处理，用ans数组表示输入这一次方向后汽车可能在的位置，每次输入方向后将不能继续前进的ans删去，将可以前进的ans更新到新的位置

  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后直接将它删去，因为对我们来说它已经没用了。接下来直接上代码

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

• 广告时间

在下的洛谷博客和博客园