学姐的层层面具

这道题是一道搜素迷宫板子题，我们使用dfs和bfs都可以去写 给的数据链很小 减枝的判断条件都是相同的

本题的目的就是找全所有的面具同时找到出口 我们就输出YES 否则输出NO

然后我们通过题面 又得知了 迷宫的一些规则 所以就可以这么写：

1. 不能出走迷宫->所以我们考虑要写一个边界判断

if (xx < 1 || xx > n || yy < 1 || yy > m)
         {
             continue;
         }

** **2.不能走到陷阱上面

if (mp[xx][yy] == 2)
         {
             continue;
         }

** **3.找到3的时候代表找到了学姐的面具 就可以统计数量使+1

if (mp[x][y] == 3)
     {
         cnt++;
     }

**然后我们就再加上很套路的搜素内容 **

1. 搜素的方向

int dx[] = {-1, 0, 1, 0};
 int dy[] = {0, 1, 0, -1};

2. 搜素开的标记数组

int vis[100][100];

3. 终止条件 如果找到出口 同时满足找到所有的面具 那么我们就标记为flag

if (x == n && y == m && cnt == k)
     {
         flag = 1;
         return;
     }

然后从入口开始找 就可以愉快AC了

DFS

#include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; // ????2?60??
 typedef pair<int, int> pii;
 int dx[] = {-1, 0, 1, 0};
 int dy[] = {0, 1, 0, -1};
 int mp[100][100];
 int vis[100][100];
 int n, m, k;
 int flag = 0;
 int cnt = 0;
 void dfs(int x, int y)
 {
 ​
     if (flag)
         return;
 ​
     if (mp[x][y] == 3)
     {
         cnt++;
     }
 ​
     vis[x][y] = 1;
     // cerr << x << " " << y << endl;
     if (x == n && y == m && cnt == k)
     {
         flag = 1;
         return;
     }
 ​
     for (int i = 0; i < 4; i++)
     {
         int xx = dx[i] + x;
         int yy = dy[i] + y;
         
         if (xx < 1 || xx > n || yy < 1 || yy > m)
         {
             continue;
         }
         
         if (mp[xx][yy] == 1)
         {
             continue;
         }
 ​
         if (mp[xx][yy] == 2)
         {
             continue;
         }
 ​
         if (vis[xx][yy] == 1)
         {
             continue;
         }
 ​
 ​
 ​
         dfs(xx, yy);
     }
 }
 void solve()
 {
 ​
     cin >> n >> m >> k;
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= m; j++)
         {
             cin >> mp[i][j];
         }
     }
 ​
     dfs(1, 1);
 ​
     if (flag == 1 && cnt == k)
     {
         cout << "YES" << endl;
     }
     else
     {
         cout << "NO" << endl;
     }
 }
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     // cin>>t;
     while (t--)
     {
         solve();
     }
     return 0;
 }

BFS

BFS 判断条件什么都是一样的 不同的只是 BFS是用队列去实现 而DFS是用内置的栈也就是递归去实现的

BFS 是类似于扩散一样 而DFS是一条路走到黑 然后再回溯回来

BFS 就是和上课讲的一样 我们存入坐标 然后去走四个方向

#include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; // ????2?60??
 typedef pair<int, int> pii;
 struct QWQ
 {
     int x,y;
 };
 int dx[] = {-1, 0, 1, 0};
 int dy[] = {0, 1, 0, -1};
 int mp[100][100];
 int vis[100][100];
 int n, m, k;
 int flag = 0;
 int cnt = 0;
 void bfs(int x, int y)
 {
     queue<QWQ>que;
     que.push({x,y});
 ​
     while(que.size())
     {
         QWQ p=que.front();
         que.pop();
 ​
         int x=p.x;
         int y=p.y;
 ​
         if (mp[x][y] == 3)
         {
             cnt++;
         }
  
         if (x == n && y == m && cnt == k)
         {
             flag = 1;
             return;
         }
 ​
         for (int i = 0; i < 4; i++)
         {
             int xx = dx[i] + x;
             int yy = dy[i] + y;
 ​
             if (xx < 1 || xx > n || yy < 1 || yy > m)
             {
                 continue;
             }
 ​
             if (mp[xx][yy] == 1)
             {
                 continue;
             }
 ​
             if (mp[xx][yy] == 2)
             {
                 continue;
             }
 ​
             if (vis[xx][yy] == 1)
             {
                 continue;
             }
 ​
             vis[xx][yy] = 1;
             que.push({xx, yy});
         }
     
     }
 ​
 }
 void solve()
 {
 ​
     cin >> n >> m >> k;
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= m; j++)
         {
             cin >> mp[i][j];
         }
     }
 ​
     bfs(1, 1);
 ​
     if (flag == 1 && cnt == k)
     {
         cout << "YES" << endl;
     }
     else
     {
         cout << "NO" << endl;
     }
 }
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     // cin>>t;
     while (t--)
     {
         solve();
     }
     return 0;
 }