1-对dfs,bfs的再认识-滑雪问题，填涂颜色

7-5 初稿

大二下学期主要学习的课程以及AI有些知识，现在重拾经典算法。

以下几道题，是有关dfs,bfs 的题目：

以下是我的经验分享：

dfs深搜索，一般会剪枝，或者用到回溯

会遇到的问题：

1. 就是可能会递归深度会非常深，需要巧妙的剪枝----怎么剪枝？

   在搜索空间树种，某一节点以下的枝显然不会找到最优解等，可以结合数学知识或者经验剪去这样的枝干。比如：下面的滑雪问题，当前长度加上当前的高度也没有最大值大，那么就剪去该枝干。

2. 可能需要记录你的路径或者过程值，以便再次遇到这种情况么就不用在递归寻找。在下面的滑雪问题，也存在。

bfs广度搜索，一般用于求解最小，最少等问题，会与优先队列等问题结合。

与dfs的侧重点不一样，但是dfs可以解决的，bfs也可以解决。

填涂颜色：

这道题，类似于围城，或者灌水。

我的思路是：把四周的0给找出来，并dfs或者bfs将他们有0的区域联通，最后没有找到的0就标为2

完整代码： https://gitee.com/moluggg/code/blob/master/%E6%BB%91%E9%9B%AA%EF%BC%8C%E5%A1%AB%E6%B6%82%E9%A2%9C%E8%89%B2.cpp

bfs解决方法：

//bfs结构：
int bfs(){//对周围染色 	while (!q.empty()){//找到队首元素，并出队	node qq = q.front();q.pop();//向四周继续拓展，加入可行点for (int i =0;i<4;i++){int x = qq.xx+dx[i];int y = qq.yy+dy[i];if (flag[x][y]==0&&a[x][y]==0){//周围复制成-1 flag[x][y] =1;//指的是访问过得 q.push(node {x,y});//}}}

dfs解决：

void dfs(int p,int q){int i;if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return;//如果搜过头或者已经被搜过了或者本来就是墙的就往回a[p][q]=1;//染色for (i=1;i<=4;i++) dfs(p+dx[i],q+dy[i]);//向四个方向搜索
}

滑雪问题：

完整代码： [https://gitee.com/moluggg/code/blob/master/%E6%BB%91%E9%9B%AA%EF%BC%8C%E5%A1%AB%E6%B6%82%E9%A2%9C%E8%89%B2.cpp](https://gitee.com/moluggg/code/blob/master/滑雪，填涂颜色.cpp)

这道题，就要边dfs边记录当前点的最优解

从左上角开始，按照题目规则，找到以该点为起点的最长路径，并记录在answer[][]里面，这样，后面万一有点到达该点除的时候，就不用了再往下递归了。

解决办法，就是回溯的时候，将answer更新（赋值）----从最低点往上，没经过一个点有四个方向，选择最长的方向的长度，这样一直更新到该点。

后面遇到已经遍历过的就直接赋值。

int dfs(int x,int y ){int flag=0;for (int i=0;i<4;i++){//四个方向int xx= dx[i]+x;int yy = dy[i]+y;if(xx>0&&xx<=n&&yy>0&&yy<=m && a[xx][yy]<a[x][y]) {//符合题目要求的点flag=1;if (answer[xx][yy]) {//遍历过，就直接赋值answer[x][y]=max(1+answer[xx][yy],answer[x][y]);}   //否则，继续dfselse answer[x][y] = max(dfs(xx,yy)+1,answer[x][y]);	} 	}if (flag==0){answer[x][y]=1;return 1;//到达最低点} return answer[x][y];//}

剪枝： 当前长度+最高高度也无法比最优解更好

在方法二中：

for(i=0;i<R;i++){for(j=0;j<C;j++){if(a[i][j]>max1)//又可以剪枝 ，只选择高度大于最长长度的点遍历{times++;dfs(i,j);}}}