• 搜索算法（DFS和BFS 蓝桥杯 C++）

    目录

    题目一（N皇后问题）： 

    代码：

     题目二（路径之谜）：

    代码：

     题目三（最大数字）：

    代码：

    题目四（长草）：

    代码：

     题目五（走迷宫）：

    代码：

     题目六（迷宫）：

    ​代码：

    题目一（N皇后问题）： 

    代码：

    1. #include
    2. using namespace std;
    3. int ans = 0;
    4. int n;
    5. int a[20] = { 0 };
    6. int judge(int k)
    7. {
    8.     for (int i = 1; i < k; i++)//从第一行到第k-1行上有无与第k行第a[k]列冲突的皇后
    9.     {
    10.         if ((abs(k - i) == abs(a[k] - a[i])) || (a[k] == a[i]))//斜线和同一列
    11.             return 0;//同一斜线说明斜率为1或者-1，则x1-x2/y1-y2=1,即x1-x2=y1-y2
    12.     }
    13.     return 1;
    14. }
    15.  
    16. int check(int a)
    17. {
    18.     if (a > n)
    19.         ans++;
    20.     else
    21.         return 0;
    22.     return 1;
    23. }
    24.  
    25. void dfs(int k)
    26. {
    27.     if (check(k))
    28.         return;
    29.     else
    30.     {
    31.         for (int i = 1; i <= n; i++)
    32.         {
    33.             a[k] = i;//第k个皇后放的列数
    34.             if (judge(k))//判断第k个皇后是否可放在a[k]该列
    35.                 dfs(k + 1);//可放，进行下一个皇后位置
    36.             else
    37.                 continue;//不可放，则下一列
    38.         }
    39.     }
    40. }
    41. int main()
    42. {
    43.     cin >> n;
    44.     dfs(1);//从第一个皇后开始放
    45.     cout << ans << endl;
    46. }

     题目二（路径之谜）：

    代码：

    1. #include
    2. #include
    3. using namespace std;
    4. int rol[25], col[25];
    5. int n;
    6. int book[25][25];//标记是否走过
    7. int dx[4] = { 0,1,-1,0 };
    8. int dy[4] = { 1,0,0,-1 };
    9. typedef struct node
    10. {
    11.     int a, b;
    12. }node;
    13. vector  res;
    14. int check(int x, int y)
    15. {
    16.     if (x == n && y == n)//走到终点
    17.     {
    18.         for (int i = 1; i <= n; i++)
    19.         {
    20.             if (col[i] != 0 || rol[i] != 0)//有一个箭靶上面还有箭，则说明不符合
    21.                 return 0;
    22.         }
    23.         for (int i = 0; i < res.size(); i++)//箭靶都拔光了，符合
    24.         {
    25.             int tx = res[i].a;
    26.             int ty = res[i].b;
    27.             int sum = n * (tx - 1) + ty - 1;//算出第几格，输出
    28.             cout << sum << " ";
    29.         }
    30.         return 0;
    31.     }
    32.     return 1;//没走到终点，继续走
    33. }
    34. void dfs(int x, int y)
    35. {
    36.     if (!check(x, y))//判断是否继续往下走
    37.         return;
    38.     else
    39.     {
    40.         for (int i = 0; i < 4; i++)//朝四个方向走
    41.         {
    42.             int tx = dx[i] + x;
    43.             int ty = dy[i] + y;
    44.             if (book[tx][ty] == 1 || tx<1 || tx>n || ty<1 || ty>n || col[tx] <= 0 || rol[ty] <= 0)//走过或者走出边界或者箭靶上的箭数量不够(等于0也不行,是因为在之前已经判断还没走到终点，如果箭的数量等于0，也意味着不可以走到这)
    45.                 continue;
    46.             else
    47.             {
    48.                 book[tx][ty] = 1;//标记该点走过
    49.                 col[tx]--, rol[ty]--;//靶子上的数减1
    50.                 res.push_back({ tx,ty });//走过的存下
    51.                 dfs(tx, ty);//从tx,ty往下走递归
    52.                 res.pop_back();//恢复
    53.                 book[tx][ty] = 0;
    54.                 col[tx]++;
    55.                 rol[ty]++;
    56.             }
    57.         }
    58.     }
    59. }
    60. int main()
    61. {
    62.     cin >> n;
    63.     for (int i = 1; i <= n; i++)
    64.         cin >> rol[i];
    65.     for (int i = 1; i <= n; i++)
    66.         cin >> col[i];
    67.     book[1][1] = 1;
    68.     rol[1]--, col[1]--;
    69.     res.push_back({ 1,1 });
    70.     dfs(1, 1);
    71.     //cout << 1;
    72. }

     题目三（最大数字）：

    代码：

    1. #include
    2. using namespace std;
    3. string s;
    4. long long ans = 0;
    5. int n, m;
    6. void dfs(int i, long long sum)
    7. {
    8.     int x = s[i] - '0';//第i位数
    9.     if (s[i])//有该位数
    10.     {
    11.         int t = min(n, 9 - x);//看操作数一的次数够不够满足该位加到9
    12.         n -= t;
    13.         dfs(i + 1, sum * 10 + x + t);
    14.         n += t;//回溯
    15.         if (m >= x + 1)//对于操作数二，只有够让该位减为9，才能使其变大
    16.         {
    17.             m -= x + 1;
    18.             dfs(i + 1, sum * 10 + 9);
    19.             m += x + 1;//回溯
    20.         }
    21.     }
    22.     else
    23.         ans = max(ans, sum);//取最大值
    24. }
    25. int main()
    26. {
    27.     cin >> s;
    28.     cin >> n >> m;
    29.     dfs(0, 0);
    30.     cout << ans;
    31. }

    题目四（长草）：

    代码：

    1. #include
    2. #include
    3. using namespace std;
    4. int n, m, k;
    5. char s[1010][1010];
    6. int dx[4] = { 1,0,0,-1 };
    7. int dy[4] = { 0,1,-1,0 };
    8. int len;
    9. typedef struct node
    10. {
    11.     int x, y;
    12. }node;
    13. queue q;
    14. void bfs()
    15. {
    16.     while (!q.empty()&&k>0)
    17.     {
    18.         int x = q.front().x ;
    19.         int y = q.front().y ;
    20.         q.pop();
    21.         for (int i = 0; i < 4; i++)//四个方向
    22.         {
    23.             int tx = x + dx[i];
    24.             int ty = y + dy[i];
    25.             if (tx < 1 || tx>n || ty < 1 || ty>m || s[tx][ty]=='g')
    26.                 continue;
    27.             else 
    28.             {
    29.                 s[tx][ty] = 'g';
    30.                 q.push({ tx, ty });
    31.             }
    32.         }
    33.         len--;//每取一块地，则len--
    34.         if (len == 0)//len等于0则表明，该月都长完了
    35.         {
    36.             k--;//则k--
    37.             len = q.size();//再取该月有多少地要向周围生长
    38.         }
    39.     }
    40. }
    41. int main()
    42. {
    43.     cin >> n >> m;
    44.     for (int i = 1; i <= n; i++)
    45.         for (int j = 1; j <= m; j++)
    46.         {
    47.             cin >> s[i][j];
    48.             if (s[i][j] == 'g')
    49.             {
    50.                 q.push({ i,j });//是草的入队
    51.             }
    52.         }
    53.     cin >> k;
    54.     len = q.size();//初始一共有几块地为草
    55.     bfs();
    56.     for (int i = 1; i <= n; i++)
    57.     {
    58.         for (int j = 1; j <= m; j++)
    59.         {
    60.             cout << s[i][j];
    61.         }
    62.         cout << endl;
    63.     }
    64. }

     题目五（走迷宫）：

    代码：

    1. #include
    2. #include
    3. using namespace std;
    4. int n, m, k;
    5. int s[110][110];
    6. int book[110][110] = { 0 };
    7. int dx[4] = { 1,0,0,-1 };
    8. int dy[4] = { 0,1,-1,0 };
    9. int flag = 0;//标志是否能走通迷宫
    10. typedef struct node
    11. {
    12.     int x, y, s;
    13. }node;
    14. node start, end1;
    15. queue q;
    16. int check(int x, int y)//检查是否到达出口
    17. {
    18.     if (x == end1.x && y == end1.y)
    19.         return 1;
    20.     return 0;
    21. }
    22. void bfs()
    23. {
    24.     while (!q.empty())
    25.     {
    26.         int x = q.front().x;//取x坐标
    27.         int y = q.front().y;//取y坐标
    28.         int step = q.front().s;//取步数
    29.         q.pop();
    30.         if (check(x,y))//检查是否到达出口
    31.         {
    32.             cout << step;
    33.             flag = 1;//标记走出迷宫
    34.             return;
    35.         }
    36.         for (int i = 0; i < 4; i++)//遍历四个方向
    37.         {
    38.             int tx = x + dx[i];
    39.             int ty = y + dy[i];
    40.             if (tx<1 || ty<1 || tx>n || ty>m || book[tx][ty]==1 ||s[tx][ty]==0)//是否越界，是否走过，是否可走
    41.                 continue;
    42.             else
    43.             {
    44.                 book[tx][ty] = 1;
    45.                 q.push({ tx,ty,step+1 });
    46.             }
    47.         }
    48.     }
    49. }
    50. int main()
    51. {
    52.     cin >> n >> m;
    53.     for(int i=1;i<=n;i++)
    54.         for (int j = 1; j <= m; j++)
    55.         {
    56.             cin >> s[i][j];
    57.         }
    58.     cin >> start.x >> start.y >> end1.x >> end1.y;
    59.     q.push({ start.x,start.y,0 });
    60.     bfs();
    61.     if (flag == 0)
    62.         cout << "-1";
    63. }

     题目六（迷宫）：

     代码：

    1. #include
    2. #include
    3. using namespace std;
    4. string s[100] = { "01010101001011001001010110010110100100001000101010",
    5.            "00001000100000101010010000100000001001100110100101",
    6.            "01111011010010001000001101001011100011000000010000",
    7.            "01000000001010100011010000101000001010101011001011",
    8.            "00011111000000101000010010100010100000101100000000",
    9.            "11001000110101000010101100011010011010101011110111",
    10.            "00011011010101001001001010000001000101001110000000",
    11.            "10100000101000100110101010111110011000010000111010",
    12.            "00111000001010100001100010000001000101001100001001",
    13.            "11000110100001110010001001010101010101010001101000",
    14.            "00010000100100000101001010101110100010101010000101",
    15.            "11100100101001001000010000010101010100100100010100",
    16.            "00000010000000101011001111010001100000101010100011",
    17.            "10101010011100001000011000010110011110110100001000",
    18.            "10101010100001101010100101000010100000111011101001",
    19.            "10000000101100010000101100101101001011100000000100",
    20.            "10101001000000010100100001000100000100011110101001",
    21.            "00101001010101101001010100011010101101110000110101",
    22.            "11001010000100001100000010100101000001000111000010",
    23.            "00001000110000110101101000000100101001001000011101",
    24.            "10100101000101000000001110110010110101101010100001",
    25.            "00101000010000110101010000100010001001000100010101",
    26.            "10100001000110010001000010101001010101011111010010",
    27.            "00000100101000000110010100101001000001000000000010",
    28.            "11010000001001110111001001000011101001011011101000",
    29.            "00000110100010001000100000001000011101000000110011",
    30.            "10101000101000100010001111100010101001010000001000",
    31.            "10000010100101001010110000000100101010001011101000",
    32.            "00111100001000010000000110111000000001000000001011",
    33.            "10000001100111010111010001000110111010101101111000" };
    34. int n, m, k;
    35. int book[110][110] = { 0 };
    36. int dx[4] = { 1,0,0,-1 };
    37. int dy[4] = { 0,-1,1,0 };
    38. string dt[4] = { "D","L","R","U" };//按字典序排序
    39. typedef struct node
    40. {
    41.     int x, y;
    42.     string t;
    43. }node;
    44. node start, end1;
    45. queue q;
    46. int check(int x, int y)//检查是否到达出口
    47. {
    48.     if (x == end1.x && y == end1.y)
    49.         return 1;
    50.     return 0;
    51. }
    52. void bfs()
    53. {
    54.     while (!q.empty())
    55.     {
    56.         int x = q.front().x;//取x坐标
    57.         int y = q.front().y;//取y坐标
    58.         string t = q.front().t;//取步骤
    59.         q.pop();
    60.         if (check(x, y))//检查是否到达出口
    61.         {
    62.             cout << t;
    63.             return;
    64.         }
    65.         for (int i = 0; i < 4; i++)//遍历四个方向
    66.         {
    67.             int tx = x + dx[i];
    68.             int ty = y + dy[i];
    69.             string tt = t + dt[i];
    70.             if (tx<0 || ty<0 || tx>29 || ty>49)//是否越界
    71.                 continue;
    72.             else if(book[tx][ty]==0&&s[tx][ty]=='0')
    73.             {
    74.                 book[tx][ty] = 1;
    75.                 q.push({ tx,ty,tt });
    76.             }
    77.         }
    78.     }
    79. }
    80. int main()
    81. {
    82.     start.x = 0, start.y = 0, end1.x = 29, end1.y = 49;
    83.     q.push({ 0,0 ,"" });
    84.     bfs();
    85. }

  • 相关阅读:
    C语言中的strcpy，strncpy，memcpy，memmove，memset函数strcmp
    真·生产力「GitHub 热点速览」
    秋招还没Offer怎么办？
    13.爱芳地产项目小程序全栈项目经验之uniapp
    CVE-2022-25845 反序列化漏洞分析
    基于centos7构建nginx的keepalived高可用集群
    openVPN
    Go入门教程
    认识与学习bash
    猿创征文 |【SpringBoot】SSM“加速器”SpringBoot初体验
  • 原文地址：https://blog.csdn.net/qq_74156152/article/details/136431978