深搜先从一条分支进行纵向搜到底，然后再从另一条分支搜到底，把所有的情况都遍历一遍。并且每一个节点只能遍历一次。 ![] 框架： DFS(N) //N代表目前DFS的深度 { if(找到解) //进行相应的操作 { … return; } for(inti=0;i<4;i++) //枚举四个方向 { DFs(N+1); //进入下层递归 } }
话说大诗人李白，一生好饮。幸好他从不开车。 一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱： 无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
#include <iostream> #include<cstdio> using namespace std; int ANS=0; char a[16]; void DFS(int N,int ans,int f,int s)//N带表深度，ans代表酒，f代表剩余遇到花的次数。 //s带表剩余遇到店的次数。 { if(ans<0)return; //当酒没有了的时候，答案肯定不对所以直接跳出循环。 if(N==14) //当剩余酒是2的时候并且深度进行到14的时候则表示符合条件。 { ANS++; //方案个数加1； for(int i=1; i<16; i++)//一次输出此时数组元素； printf("%c",a[i]); printf("\n"); return; } else { if(s) { a[N]='a'; DFS(N+1,ans*2,f,s-1); } if(f) { a[N]='b'; DFS(N+1,ans-1,f-1,s); } } } int main() { int ans=2; a[0]=' '; a[15]='b';//已知最后一次遇见的是花，所以可以推测出倒数第二次遇见的也是花。 a[14]='b'; DFS(1,ans,8,5);// printf("%d\n",ANS); }广搜是先进行横向遍历，其特点是尽可能先对横向进行搜索,从指的出发点,按照该点的路径长度由短到长的顺序访问图中各顶点。记住横向遍历是一个一个来，并不是同时对所有相邻的节点进行访问。 城堡问题
#include <map> #include <set> #include <cmath> #include <deque> #include <queue> #include <stack> #include <cstdio> #include <cctype> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define INF 0x7fffffff using namespace std; int n, m; int room[55][55]; int color[55][55]; int color_num, max_room; int tmp_room; void dfs(int i, int j) { if(color[i][j]) { return; } color[i][j] = color_num; tmp_room ++; if((room[i][j] & 1) == 0) dfs(i, j - 1);//巧妙运用位运算，来判断是否有墙，且这里位运算要加上括号，因为位运算优先级较低 if((room[i][j] & 2) == 0) dfs(i - 1, j); if((room[i][j] & 4) == 0) dfs(i, j + 1); if((room[i][j] & 8) == 0) dfs(i + 1, j); } int main() { while(scanf("%d %d", &n, &m) != EOF) { for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { scanf("%d", &room[i][j]); } } color_num = 0, max_room = 0; memset(color, 0, sizeof(color)); for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { tmp_room = 0;//判断每一个连通分量（即房间）里的大小 if(color[i][j] == 0) { color_num ++; dfs(i, j); max_room = max(max_room, tmp_room);//取最大值 } } } printf("%d\n%d\n", color_num, max_room); } return 0; }