深搜（备忘录）
2026-02-12 14:12:30
发布于：浙江
1.1
二维数组
搜索连通块
（地图，迷宫）
#include<bits/stdc++.h>
using namespace std;
//怎么找连通块的数量
int n,m,ans;
char a[1005][1005];
bool vis[1005][1005];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};//方向数组，上下左右
void dfs(int x,int y){//找这个连通块中的所有点，并且全部标记上
//标记这个点
vis[x][y]=1;
//搜下一个点
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m)continue;//越界了不行
if(vis[xx][yy]||a[xx][yy]!='#')continue;//标记过了或者不是连通块也不行
dfs(xx,yy);
}
}
int main(){
cin>>n>>m;
//搜很多次，每个连通块搜一次，每搜一次，连通块+1
//搜没标记的点
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]0&&a[i][j]'#'){
dfs(i,j);
++ans;
}
}
}
cout<<ans;
return 0;
}
1.2
邻接矩阵
（图，点，边）
一维
#include<bits/stdc++.h>
using namespace std;
//怎么找连通块的数量
//方向数组，上下左右
void dfs(int now){//找这个连通块中的所有点，并且全部标记上
//标记这个点
vis[now]=1;
//搜下一个点
int main(){
//搜很多次，每个连通块搜一次，每搜一次，连通块+1
//搜没标记的点
vector<int>ve;//动态数组，自由在末尾添加一个数字
ve[i].push_back(j);//邻接表，i，j相连
ve[].push_back()
g[i][j]=g[i][j]=1;//邻接矩阵
//邻接表怎么找U连接的所有点
for(int i=0;i<[u].size();i++){
cout<<ve[u][i]<<" ";
}
for(int i:ve[u]){
cout<<i<<" ";
}
//邻接矩阵怎么找u连接的所有点
for(int i=1;i<=n;i++){
if(g[u][i]==1){
cout<<i<<" ";
}
}
return 0;
}
这里空空如也
有帮助，赞一个