dfs连通块 迷宫类问题总结 bfs解题步骤 树与图的存储与遍历

一·连通块问题拿登录 - 评测平台最大黑区域这道题举例先将图建好之后进入dfs函数找到一个黑像素对它进行拓展将拓展到的像素变为0再将面积加1 拓展完后将面积与目前最大面积比较 大于最大面积就最大面积当前面积 以此类推 全部遍历完后 输出最大黑面积int dfs(int x,int y) { if(a[x][y]1)//当前像素 { sum;//当前面积 a[x][y]0; if(a[x-1][y]1) dfs(x-1,y); if(a[x1][y]1) dfs(x1,y); if(a[x][y-1]1) dfs(x,y-1); if(a[x][y1]1) dfs(x,y1); } else { if(y1m) dfs(x1,1); dfs(x,y1); } return maxsmax(maxs,sum); }二·迷宫类问题以登录 - 评测平台迷宫寻路这道题为例先输入长 宽 图之后进入dfs函数从起点11开始向上下左右四个方向进行状态拓展拓展完后判断是否到达终点n,m如果到达则将标记变量改为1 表示能走到 等到dfs执行完后判断标记变量是否为1 如果是则输出yes 否则输出no程序#includebits/stdc.h using namespace std; int n,m,flag; char a[105][105]; int f[105][105]; void dfs(int x,int y) { if(x1||y1||xn||ym) return ; if(a[x][y]#) return ; if(fl[x][y]1) return ; if(xnym) { flag1; return ; } f[x][y]1; f(x-1,y); f(x1,y); f(x,y-1); f(x,y1); } int main() { cinnm; for(int i1;in;i) { for(int j1;jm;j) { cina[i][j]; } } dfs(1,1); if(flag1) { coutYes; } else { coutNo; } return 0; }三.bfs解题步骤以https://www.luogu.com.cn/problem/P1443马的遍历这道题为例首先输入长宽和马的位置sx,sy之后清空队列进入bfs函数 先将起点推入到队列中 并标记防止重复遍历导致死循环 根据题目要求输入马到起点要几步到a数组里 再获取队首元素 之后将队首元素推出队列 进行状态拓展 再根据题目要求输入马到当前点要多少步到a数组里 最后输出a数组里的马到每个点所需的步数程序#includeiostream #includequeue #includecstring using namespace std; struct node{ int x,y,step; }; int n,m,sx,sy; int f[405][405],a[405][405],X[15]{1,2,2,1,-1,-2,-2,-1},Y[15]{-2,-1,1,2,2,1,-1,-2}; queuenode q; void bfs() { q.push({sx,sy,0}); f[sx][sy]1; a[sx][sy]0; while(q.size()) { node hq.front(); q.pop(); for(int i0;i8;i) { int dx,dy; dxh.xX[i]; dyh.yY[i]; if(f[dx][dy]0dx1dy1dxndym) { f[dx][dy]1; a[dx][dy]h.step1; q.push({dx,dy,h.step1}); } } } } int main() { cinnmsxsy; memset(a,-1,sizeof(a)); bfs(); for(int i1;in;i) { for(int j1;jm;j) { couta[i][j] ; } coutendl; } return 0; }四.树与图的存储和遍历1树的存储和遍历树的存储方式1邻接表vector int a; int n//共有n条节点连接的线段 cinn; a.resize(n5); for(int i1;in;i) { int u,v;//线段的两个节点 cinuv; a[u].push_back(v); a[v].push_back(u); }(2)结构体数组struct node{ int l,r; }a[100005]; int main() { int n,i; cinn; for(i1;in;i) { cina[i].la[i].r; } }树的遍历以这道题为例登录 - 评测平台在树存储好后进入dfs 先根据题目要求判断当前节点是否有左右子节点 如果满足条件则输出否则进行遍历 判断是否有左 右 子节点并推入队列进行判断是否满足条件#includeiostream #includequeue using namespace std; const int N1e55; struct node{ int l,r; }a[N]; struct str{ int x,step; }; queuestr q; void bfs() { while(q.size()) { str tq.front(); q.pop(); int nxt.x; if(a[nx].l0a[nx].r0) { coutt.step; return ; } if(a[nx].l) q.push({a[nx].l,t.step1}); if(a[nx].r) q.push({a[nx].r,t.step1}); } } int main() { int n,i; cinn; for(i1;in;i) { cina[i].la[i].r; } q.push({1,1}); bfs(); return 0; }图的存储1领接表无向图vector int a; int n cinn; a.resize(n5); for(int i1;in;i) { int u,v; cinuv; a[u].push_back(v); a[v].push_back(u); }有向图vector int a; int n cinn; a.resize(n5); for(int i1;in;i) { int u,v; cinuv; a[u].push_back(v); }领接矩阵无向图vector vectorint a; int n,m; int main() { int i,u,v; cinnm; for(i1;in;i) { a.resize(n5); } for(i1;in;i) { cinuv; cina[u][v]; cina[v][u]; } return 0 }有向图vector vectorint a; int n,m; int main() { int i,u,v; cinnm; for(i1;in;i) { a.resize(n5); } for(i1;in;i) { cinuv; cina[u][v]; } return 0 }图的遍历宽搜遍历vector vectorint a; int n,m; queueint q; int flag[100005]; void bfs() { q.push(1); flag[1]1; while(q.size()) { int x; xq.front(); q.pop(); coutx ; for(int i0;ia[x].size();i) { if(flag[a[x][i]]0) { flag[a[x][i]]1; q.push(a[x][i]); } } } }