MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 P1189 【SEARCH】

posted on 2018-04-01 16:17:27 | under 题解 |

先反省一波:我以后再也不用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;
}
  • 广告时间

在下的洛谷博客博客园