心得体会
今天整理了一下自己对dfs深度搜索的基础的理解 试着做了两道题。感觉从接触算法开始对问题的抽象程度开始慢慢变高，然后每次改自己代码的逻辑都改的很想④
学习内容
dfs深度搜索基础
（以下是苯人对dfs的基础知识的理解）
实际在处理问题的时候只记住了“深入浅出”或者是“不撞南墙不回头” 的特性，需不需要标记，需不需要计数，都根据题目的实际需要确定
迷宫
给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 SX,SY,FX,FY，SX,SY 代表起点坐标，FX,FY 代表终点坐标。
接下来 T 行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
输入输出样例
输入 #1
2 2 1
1 1 2 2
1 2
输出 #1
1
题目理解
非常经典的dfs入门题，这里只写出处理问题的思路。这里实际做题的时候数据规模很小，所以对于更大的数据规模不确定是否适用
定变量（这里N M T 终点的坐标都是全局变量，起点坐标全局 局部都可以），行动数组next,标记数组book，自定义函数dfs(这里使用void类型），函数体首先判断当前格子是否“合法”（障碍格、终点格、越界、重复），当一组数据全都通过判断时，表明：当前站着的这一格没问题，可以往下走；所以问题变成：下一步怎么走？
然后根据题目要求探索可能性（用next数组对坐标进行处理，然后别忘记设下标记 结束时撤销标记），最后输出方法数就好了
代码
#include
int N,M,T;
int x,x2,y,y2,cnt;
int book[5][5],block[10][2], next[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y)
{
for(int i=0;i { if(x==block[i][0]&&y==block[i][1]) return ; } if(x==x2&&y==y2)//判断终点 { cnt++; return ; } for(int i=0;i<4;i++) { if(x+next[i][0]<1||x+next[i][0]>N||y+next[i][1]<1||y+next[i][1]>M) continue; if(book[y+next[i][1]-1][x+next[i][0]-1]==1) continue; book[y-1][x-1]=1; dfs(x+next[i][0],y+next[i][1]); book[y-1][x-1]=0; } return ; } int main() { scanf("%d %d %d",&N,&M,&T); scanf("%d %d %d %d",&x,&y,&x2,&y2); for(int i=0;i scanf("%d %d",&block[i][0],&block[i][1]); dfs(x,y); printf("%d",cnt); return 0; } 这里在判断的时候，把条件分了下类，变成出口判断条件和搜索条件，然后先判断障碍再判断终点（因为我刚开始写的是先判断终点再判断障碍，ac只有90） P1596 [USACO10OCT] Lake Counting S/农夫水坑 由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 �×�(1≤�≤100,1≤�≤100)N×M(1≤N≤100,1≤M≤100) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。 输入第 11 行：两个空格隔开的整数：�N 和 �M。 第 22 行到第 �+1N+1 行：每行 �M 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。 输出一行，表示水坑的数量。 题目理解 （这道题细节很多，我的思路很粗糙，各位实操的时候多多注意） 首先这个问题不是一个类似“方法数”或者“最短路径”问题，但是它点到了DFS一个特性——“相连性”（类似蓝桥杯 剪邮票那道题的一个思路：先全排列 再借助DFS的相连性进行判断） 这个题目的意思是一组W就是一个水坑，当W格周围一圈还有其他W且不重复的时候，就是“相连”。这里要注意的是，一个孤立的W也是一个水坑（就是一个W被一圈.包围） 我这里自定义了dfs函数用于判断相连，所以它的出口条件就是，被判断格 的 周围一圈没有W。然后借助了一个计数变量计算W的数量，从而计算水坑的数量 又因为每个水坑相连且不重复 且多次判断，所以我们这里是 每判断一个W就留下标记且不撤销标记。 代码 //这里先看一下题目的输入数据例子 /* 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. */ //首先第一行是NxM 然后回车 再输入W. //但是scanf是不吃回车的，对W的处理我使用的是二维字符型数组 //这样会导致缓冲区留下一个回车 会直接被数组录入，这是我们不需要的 //所以给出char型变量ch用来吃掉我们不需要的字符 #include int next[8][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}}; int book[100][100],N,M,cnt; char field[100][100]; void dfs(int x,int y) { for(int i=0;i<8;i++) { if(x+next[i][0]<1||x+next[i][0]>M||y+next[i][1]<1||y+next[i][1]>N) { //printf("越界\n"); continue; } else { if(field[y+next[i][1]-1][x+next[i][0]-1]=='W') { if(book[y+next[i][1]-1][x+next[i][0]-1]==0) { book[y+next[i][1]-1][x+next[i][0]-1]=1; cnt++; dfs(x+next[i][0],y+next[i][1]); } //else //printf("重复\n"); } //else //printf("旱地\n"); } } return ; } int main() { scanf("%d %d",&N,&M); char ch=getchar();//吃回车 for(int i=0;i { for(int j=0;j scanf("%c",&field[i][j]); ch=getchar();//吃回车 } int num=0; //这里是找‘W’ //因为有标记的关系，所以完成对一个水坑的的判断之后，对于下一个水坑的起点 //我们只要找到新的一个没有标记的W就好 for(int i=0;i { for(int j=0;j { if(field[i][j]=='W'&&book[i][j]==0) { cnt=1; book[i][j]=1; dfs(j+1,i+1); //printf("%d %d %d\n",j+1,i+1,cnt); if(cnt>=1) num++; } } } printf("%d",num); } 这道题主要的细节是不要录入不需要的字符，所以要注意对缓冲区的处理 （我的代码里有一些输出行主要是用来检测过程，不然每次改代码都很头疼） 参考链接
发表评论