ToB企服应用市场:ToB评测及商务社交产业平台

标题: 2.18寒假 [打印本页]
作者: 写过一篇    时间: 2025-2-19 15:15
标题: 2.18寒假
今天在题单中看了搜索。

解析：两个一维数组，用于表示上下左右四个方向的偏移量，分别对应 x 轴和 y 轴的偏移，遍历四个方向（左、右、下、上），对于每个方向，检查目标位置是否未走过（temp[x + dx][y + dy] == 0）且不是停滞（map[x + dx][y + dy] == 1）。如果满足条件，将当前位置标记为已走过（temp[x][y] = 1），然后递归调用 walk 函数继续搜索。递归返回后，将当前位置标记为未走过（temp[x][y] = 0），以便尝试其他可能的路径。起首读取舆图的长 n、宽 m 和停滞总数 T。
将舆图的全部位置初始化为可通行（map[ix][iy] = 1）。读取出发点坐标 (sx, sy) 和终点坐标 (fx, fy)。
循环 T 次，每次读取一个停滞的坐标 (l, r)，并将该位置标记为停滞（map[l][r] = 0）。
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. int map[6][6];
  5. int temp[6][6];
  6. int dx[4] = {0, 0, 1, -1};
  7. int dy[4] = {-1, 1, 0, 0};
  8. int total, fx, fy, sx, sy, T, n, m, l, r;
  9. void walk(int x, int y) {
  10.     if (x == fx && y == fy) {
  11.         total++;
  12.         return;
  13.     } else {
  14.         for (int i = 0; i <= 3; i++) {
  15.             if (temp[x + dx[i]][y + dy[i]] == 0 && map[x + dx[i]][y + dy[i]] == 1) {
  16.                 temp[x][y] = 1;
  17.                 walk(x + dx[i], y + dy[i]);
  18.                 temp[x][y] = 0;
  19.             }
  20.         }
  21.     }
  22. }
  23. int main() {
  24.     scanf("%d %d %d", &n, &m, &T);
  25.     for (int ix = 1; ix <= n; ix++) {
  26.         for (int iy = 1; iy <= m; iy++) {
  27.             map[ix][iy] = 1;
  28.         }
  29.     }
  30.     scanf("%d %d", &sx, &sy);
  31.     scanf("%d %d", &fx, &fy);
  32.     for (int u = 1; u <= T; u++) {
  33.         scanf("%d %d", &l, &r);
  34.         map[l][r] = 0;
  35.     }
  36.     walk(sx, sy);
  37.     printf("%d", total);
  38.     return 0;
  39. }
复制代码

解析：将当前位置 (o, p) 标记为 1，表示该位置已经被访问过。循环遍历四个方向（右、下、左、上），递归调用 dfs 函数继续搜索相邻位置。从矩阵的四条界限（上、下、左、右）开始调用 dfs 函数举行搜索。因为界限上的 0 肯定不会被 1 完全包围，通过 DFS 可以将与界限上的 0 相连通的全部 0 标记为 1。遍历 a 数组，如果某个位置的值仍然为 0，说明该位置的 0 被 1 完全包围，将 b 数组中对应位置的值改为 2。
  1. #include<stdio.h>
  2. int a[30][30],b[30][30];
  3. int dx[5]={0,0,1,0,-1};
  4. int dy[5]={0,1,0,-1,0};
  5. int n;
  6. void dfs(int o,int p)
  7. {
  8.         int i;
  9.         if(o<0||o>n+1||p<0||p>n+1||a[o][p]!=0){
  10.                 return;
  11.         }
  12.         a[o][p]=1;
  13.         for(i=1;i<=4;i++){
  14.                 dfs(o+dx[i],p+dy[i]);
  15.         }
  16. }
  18. int main()
  19. {
  20.         int i,j;
  21.         scanf("%d",&n);
  22.         for(i=0;i<n;i++){
  23.                 for(j=0;j<n;j++){
  24.                         scanf("%d",&a[i][j]);
  25.                         b[i][j]=a[i][j];
  26.                 }
  27.         }
  28.         for(i=0;i<n;i++)
  29.         dfs(0,i);
  30.         for(i=0;i<n;i++)
  31.         dfs(n-1,i);
  32.         for(i=0;i<n;i++)
  33.         dfs(i,0);
  34.         for(i=0;i<n;i++)
  35.         dfs(i,n-1);
  36.         for(i=0;i<n;i++){
  37.                 for(j=0;j<n;j++){
  38.                         if(a[i][j]==0)
  39.                         b[i][j]=2;
  40.                 }
  41.         }
  42.         for(i=0;i<n;i++){
  43.                 for(j=0;j<n;j++)
  44.                 printf("%d ",b[i][j]);
  45.                 printf("\n");
  46.         }
  47.         return 0;
  48. }
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4