dfs和bfs能解决的问题

一.理解暴力穷举之dfs和bfs

暴力穷举

暴力穷举是在解决问题中最常用的手段，而dfs和bfs算法则是这个手段的两个非常重要的工具。
其实，最简单的穷举法是直接遍历，如数列求和，遍历一个数组即可求得所问答案，这与我在前两篇博客中讲述的动态规划算法执行方式其实是一样的，其特点我们说过，有三个“可分解，可一次解决，可储存”，可分解是不管有多大多复杂的数据都能用同一种办法解决的前提，可一次解决，代表每一个子问题的解决答案即是当前最优解，也是全局最优解的子解，这叫做无后效性，无后效性其实表面意思是局部决策对全局决策无关，但准确来说，是局部决策的最优解之外的决策永远不会成为全局决策的子决策，最后若可储存子问题的答案，我们就可以实现直接遍历或动态规划得到我们所需要的答案。

dfs和bfs的特点

在前言我们提到了直接遍历的穷举办法，而动态规划也是其中之一，具有”可分解，可一次解决，可存储“的特点，而dfs和bfs与它们的唯一区别就是”不可一次解决“，也就是并非有最优解，子问题的每一个决策都有可能是全局解的子解，这叫做有后效性，但准确来说，是局部决策都可能会成为全局决策的子决策，那么如何解决这类问题呢，dfs和bfs算法就是这类问题的天敌。

二.掌握dfs和bfs解决问题的方法

1.dfs通过其能够“回溯”的本领解决有后效性

例题

题目链接

分析

题目问的是，在给定n*n棋盘内，棋子位置相互不冲突的情况下，摆放在棋盘区域的棋子个数为k的方案数是多少
1.可先放前面的棋子，再放后面的棋子（可分解）
2.对每个棋盘位置都有放或不放两种决策，每个棋子的这两种决策都可能满足题意（有后效性）
3.在从前到后决策的过程中，可记录已放棋子个数（可存储）

代码

#include<iostream>
#include<cstdio>using namespace std;const int N = 100;
bool col[N],row[N];
char g[N][N];
int cnt = 0,n,m;
void dfs(int x,int y,int k)
{if(x == n) return;if(k == m) {cnt++;return;}if(y == n){y = 0;x++;}dfs(x,y+1,k);//先递归遍历左子树，即不放皇后的操作if(!col[y]&&!row[x]&&(g[x][y] == '#')){col[y] = row[x] = true;dfs(x,y+1,k+1);//再递归遍历右子树col[y] = row[x] = false;}
}
int main()
{while(1){scanf("%d%d",&n,&m);if(n == -1&&m == -1) break;for(int i = 0;i<n;i++)for(int j = 0;j<n;j++)cin>>g[i][j];dfs(0,0,0);printf("%d\n",cnt);cnt = 0;}return 0;
}

2.bfs通过其能够“排队”的本领解决有后效性

例题

题目链接

分析

题目问的是，在给定L*R*C迷宫内，从“S”走到“E”至少需要多少分钟
1.可一步一步走（可分解）
2.对每一步都有上下左右前后，每一步的决策都可能满足题意（有后效性）
3.在从前到后决策的过程中，可记录已用掉多少分钟（可存储）

代码

#define _CRT_SECURE_NO_WARNINGS
//#define LOCAL
#include <iostream>
#include <cstring>
#include <queue>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=35;
int L,R,C;
int sx,sy,sz,ex,ey,ez;
bool flag;
char g[N][N][N];
bool st[N][N][N];
int dist[N][N][N];
struct Node
{int z,x,y;
};
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
void bfs(int sz,int sx,int sy)
{memset(dist,0x3f,sizeof dist);Node input;input.z=sz,input.x=sx,input.y=sy;queue<Node>q;q.push(input);st[sz][sx][sy]=1;dist[sz][sx][sy]=0;while(q.size()){Node t=q.front();if(t.z==ez&&t.x==ex&&t.y==ey){flag=1;break;}q.pop();for(int i=0;i<6;i++){int a=t.z+dz[i];int b=t.x+dx[i];int c=t.y+dy[i];if(a<0||b<0||c<0||a>=L||b>=R||c>=C)continue;if(st[a][b][c]||g[a][b][c]=='#')continue;st[a][b][c]=1;Node tmp;tmp.z=a,tmp.x=b,tmp.y=c;q.push(tmp);dist[a][b][c]=dist[t.z][t.x][t.y]+1;}}
}
void solve()
{while(~scanf("%d%d%d",&L,&R,&C)&&(L||R||C)){for(int i=0;i<L;i++)for(int j=0;j<R;j++)scanf("%s",g[i][j]);for(int i=0;i<L;i++)for(int j=0;j<R;j++)for(int k=0;k<C;k++){if(g[i][j][k]=='S')sz=i,sx=j,sy=k;if(g[i][j][k]=='E')ez=i,ex=j,ey=k;}memset(st,0,sizeof st);flag=0;bfs(sz,sx,sy);if(flag) printf("Escaped in %d minute(s).\n",dist[ez][ex][ey]);else puts("Trapped!");}return;
}int main()
{
#ifdef LOCALfreopen("data.in", "r", stdin);freopen("data.out", "w", stdout);
#endifint t = 1;//cin>>t;while(t--){solve();}return 0;
}

~感谢观看❥(^_-)