作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

今天写 搜索题

0.知识点

• DFS

  • 设计步骤

  1. 确定该题目的状态（包括边界）
  2. 找到状态转移方式
  3. 找到问题的出口、计数或者某一个状态
  4. 设计搜索

  • 代码模板

  ans  //答案，用全局变量来表示
  
  bool st[N]; //标记状态
      
  bool check(参数)
  {
  	if(满足条件)
          return 1;
      return 0;
  }
  
  void dfs(int step)
  {
  	if(判断边界)
      {
  		不在边界内，即回溯
      }
      尝试每一种可能  //for 循环
      {
  		满足check条件//if
          标记 //  bool st[]
          继续下一步 dfs(step+1)
          恢复初始状态(回溯的时候要用到)
      }
      
  }
  

• BFS

  • 前引

    一般使用队列来实现；

    BFS一般用于求最短路问题，边权为1

  • 步骤设计

    1. 确定该题目的状态（包括边界）
    2. 找到状态转移方式
    3. 找到问题的出口，计数或者某一个状态
    4. 设计搜索

    和前面的差不多，一般情况下，BFS 和 DFS 可以互换

  • 注意

    1. BFS=队列
    2. BFS：逐层扩展下一层，把扩展出的下一层状态放进队列中处理
    3. 如果这些状态有相同的，只需要搜一次，只需要进入队列一次
    4. 必须判重

1.乳草的入侵

• 题目

  链接： 189. 乳草的入侵 - AcWing题库

  农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

  可惜天不从人愿，他在植物大战人类中败下阵来。

  邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

  草地像往常一样，被分割成一个高度为 Y，宽度为 X 的直角网格。

  (1,1)是左下角的格（也就是说坐标排布跟一般的 X,Y 坐标相同）。

  乳草一开始占领了格 (Mx,My)。

  每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角线上相邻的格）内。

  1 周之后，这些新占领的格又可以把乳草传播到更多的格里面了。

  达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

  她很好奇到底乳草要多久才能占领整个草地。

  如果乳草在 0 时刻处于格 (Mx,My)，那么几个星期以后它们可以完全占领入侵整片草地呢（对给定的数据总是会发生）？

  在草地地图中，. 表示草，而 * 表示大石。

  比如这个 X=4,Y=3 的例子。

  ....
  ..*.
  .**.
  

  如果乳草一开始在左下角（第 1 排，第 1 列），那么草地的地图将会以如下态势发展：

        ....  ....  MMM.  MMMM  MMMM  
        ..*.  MM*.  MM*.  MM*M  MM*M  
        M**.  M**.  M**.  M**.  M**M  
  星期数  0     1     2     3     4
  

  乳草会在 4 星期后占领整片土地。

  输入格式

  第 1 行: 四个由空格隔开的整数: X, Y, Mx, My

  第 2 到第 Y+1 行: 每行包含一个由 X 个字符（. 表示草地，* 表示大石）构成的字符串，共同描绘了草地的完整地图。

  输出格式

  输出一个整数，表示乳草完全占领草地所需要的星期数。

  数据范围

  1≤X,Y≤100

  输入样例：

  4 3 1 1
  ....
  ..*.
  .**.
  

  输出样例：

  4
  

• 前n次 AC 0%

  #include<bits/stdc++.h>
  using namespace std;
  
  typedef pair<int,int> PII;
  
  const int N=110;
  
  int n,m,a,b;
  
  char g[N][N];
  int d[N][N];
  
  int dx[8]={0,0,-1,1,-1,1,-1,1},dy[8]={1,-1,0,0,1,1,-1,-1};
  
  bool check()  //判断是否满足条件，除了石头都是乳草
  {
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
              if(g[i][j]=='.')
                  return false;
      return true;
  }
  
  void f()  //输出调式用的
  {
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++)
          {
              cout<<g[i][j];
          }
          cout<<endl;
      }
      cout<<endl;
  }
  
  void bfs()
  {
      memset(d,-1,sizeof d);  //初始化
      
      int cnt=0;  //扩展的次数
      
      queue<PII> q;
      q.push({m-b+1,a});
      
      d[m-b+1][a]=0;
      
      //下面几乎全错，没想出来怎么一次性扩展一层
      while(q.size())
      {
          auto t=q.front();
          q.pop();
          int flag=0;
          for(int i=0;i<8;i++)
          {
              
              int x=t.first+dx[i],y=t.second+dy[i];
              if(d[x][y]==-1&&x>=1&&y>=1&&x<=n&&y<=m&&g[x][y]!='*')
              {
                  flag=1;
                  q.push({x,y});
                  d[x][y]=d[t.first][t.second]+1;
                  g[x][y]='M';
                  
              }
              if(flag) cnt++;
              if(check())
                  {
                      cout<<cnt;
                      return ;
                  }
          }
      }
      
  }
  
  int main()
  {
      cin>>n>>m>>a>>b;
      
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
              cin>>g[i][j];  //看题，起点应该从1开始，存图
              
      g[m-b+1][a]='M';  //地图的坐标 （1，1）在右下角，（a,b）在二维数组里面的表示，在纸上举个例子，模拟一下，硬想我是真不行
      
      bfs();
      
      return 0;
  }
  

• 模仿正确的题解写的 AC 0%

  #include<bits/stdc++.h>
  using namespace std;
  
  typedef pair<int,int> PII;
  
  const int N=110;
  
  int n,m;
  int ans,cnt;
  PII st;
  char g[N][N];
  int d[N][N],vis[N][N];
  int dx[8]= {1,-1,0,0,1,-1,1,-1}, dy[8]= {0,0,1,-1,1,-1,-1,1};
  
  void bfs()
  {
      queue<PII> q;
      q.push(st);
      
      d[st.first][st.second]=0;
      vis[st.first][st.second]=1;
      
      while(q.size())
      {
          auto t=q.front();
          q.pop();
          
          for(int i=0;i<8;i++)
          {
              int x=st.first+dx[i],y=st.second+dy[i];
              if(!vis[x][y]&&x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='*')
              {
                  cnt--;
                  vis[x][y]=1;
                  q.push({x,y});
                  d[x][y]=d[t.first][t.second]+1;
                  ans=max(ans,d[x][y]);
                  if(cnt==0) 
                      return ;
              }
          }
      }
  }
  
  
  int main()
  {
      scanf("%d%d%d%d\n",&n,&m,&st.second,&st.first);
      
      
      for(int i=n;i>=1;i--)
          for(int j=1;j<=m;j++)
          {
              cin>>g[i][j];
              if(g[i][j]=='.')
                  cnt++;
          }
          
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          cout<<g[i][j];
          cout<<endl;
          
      if(g[st.first][st.second]=='.') 
          cnt--;
      
      bfs();
      
      cout<<ans;
      
      return 0;
  }
  

  不知道哪错了 Debug 中

• 正确代码

  #include <bits/stdc++.h>
  using namespace std;
  #define fir(i,a,b) for(int i=a;i<=b;i++)
  #define pii pair<int,int>
  #define mk(a,b) make_pair(a,b)
  const int dx[8]= {1,-1,0,0,1,-1,1,-1};
  const int dy[8]= {0,0,1,-1,1,-1,-1,1};
  const int N=110;
  pii st,now;
  char s[N][N];
  int cnt,n,m,vis[N][N],ans,dis[N][N];
  queue<pii> q;
  int check(int x,int y)//判断:在范围;没有被访问过;不是石头
  {
      return x>=1 && x<=n && y>=1 && y<=m && vis[x][y]==0 && s[x][y]!='*';
  }
  int bfs()
  {
      q.push(st);
      dis[st.first][st.second]=0;
      vis[st.first][st.second]=1;
      while(q.size())
      {
          now=q.front();
          q.pop();
          fir(i,0,7)
          {
              int x=now.first+dx[i],y=now.second+dy[i];//拓展
              if (check(x,y))
              {
                  cnt--;
                  vis[x][y]=1;
                  dis[x][y]=dis[now.first][now.second]+1;
                  ans=max(ans,dis[x][y]);//找出最大的dis,也就是最后答案
                  q.push(mk(x,y));
                  if (cnt==0)//所有的草地被占满了.
                      return 1;
              }
          }
      }
  }
  int main()
  {
      scanf("%d%d%d%d\n",&m,&n,&st.second,&st.first);//读入真是博大精深啊!!!!!
      for(int i=n; i>=1; i--)
      {
          for(int j=1; j<=m; j++)
          {
              s[i][j]=getchar();
              if (s[i][j]=='.')
                  cnt++;//统计有多少个空
          }
          getchar();
      }
      if (s[st.first][st.second]=='.')//刚开始就有一根乳草.
          cnt--;
      bfs();
      cout<<ans;
  }
  

• 反思

  今天晚上没课，四个小时就做这个题，最后还没做出来

  • 往外扩展几层，直接就是 最短距离 d[x]

  最大的收获就是 （1，1）在左下角的坐标的表示，详细看代码

  • 中间有一次，考虑这个问题，但只是仅仅想到一个起始点的坐标，没考虑全面，整个数组都是

  今天的时间真的浪费掉了，应该及时看题解的