一.理解暴力穷举之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 LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
int t = 1;//cin>>t;
while(t--){
solve();
}
return 0;
}
~感谢观看❥(^_-)