2.18寒假

今天在题单中看了搜索。

解析：两个一维数组，用于表示上下左右四个方向的偏移量，分别对应 x 轴和 y 轴的偏移，遍历四个方向（左、右、下、上），对于每个方向，检查目标位置是否未走过（temp[x + dx[i]][y + dy[i]] == 0）且不是障碍（map[x + dx[i]][y + dy[i]] == 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）。

#include <stdio.h> #include <stdlib.h> #include <math.h> int map[6][6]; int temp[6][6]; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int total, fx, fy, sx, sy, T, n, m, l, r; void walk(int x, int y) { if (x == fx && y == fy) { total++; return; } else { for (int i = 0; i <= 3; i++) { if (temp[x + dx[i]][y + dy[i]] == 0 && map[x + dx[i]][y + dy[i]] == 1) { temp[x][y] = 1; walk(x + dx[i], y + dy[i]); temp[x][y] = 0; } } } } int main() { scanf("%d %d %d", &n, &m, &T); for (int ix = 1; ix <= n; ix++) { for (int iy = 1; iy <= m; iy++) { map[ix][iy] = 1; } } scanf("%d %d", &sx, &sy); scanf("%d %d", &fx, &fy); for (int u = 1; u <= T; u++) { scanf("%d %d", &l, &r); map[l][r] = 0; } walk(sx, sy); printf("%d", total); return 0; }

解析：将当前位置 (o, p) 标记为 1，表示该位置已经被访问过。循环遍历四个方向（右、下、左、上），递归调用 dfs 函数继续搜索相邻位置。从矩阵的四条边界（上、下、左、右）开始调用 dfs 函数进行搜索。因为边界上的 0 肯定不会被 1 完全包围，通过 DFS 可以将与边界上的 0 相连通的所有 0 标记为 1。遍历 a 数组，如果某个位置的值仍然为 0，说明该位置的 0 被 1 完全包围，将 b 数组中对应位置的值改为 2。

#include<stdio.h> int a[30][30],b[30][30]; int dx[5]={0,0,1,0,-1}; int dy[5]={0,1,0,-1,0}; int n; void dfs(int o,int p) { int i; if(o<0||o>n+1||p<0||p>n+1||a[o][p]!=0){ return; } a[o][p]=1; for(i=1;i<=4;i++){ dfs(o+dx[i],p+dy[i]); } } int main() { int i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%d",&a[i][j]); b[i][j]=a[i][j]; } } for(i=0;i<n;i++) dfs(0,i); for(i=0;i<n;i++) dfs(n-1,i); for(i=0;i<n;i++) dfs(i,0); for(i=0;i<n;i++) dfs(i,n-1); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[i][j]==0) b[i][j]=2; } } for(i=0;i<n;i++){ for(j=0;j<n;j++) printf("%d ",b[i][j]); printf("\n"); } return 0; }