1.判断点是否能到终点
int main() { 将所有点标记为新点; 起点 = x; 终点 = y; cout << dfs(起点); } bool dfs(V) { //边界条件 if(v是终点) return true; if(v是旧点) return false; 将v标记为旧点 表示要访问 for(跟v相邻的所有的点u) { //返回true表示u能到终点 所以v也可以到终点 if(dfs(u) == true) return true; } //一直到循环了所有的相邻的点 不能到达终点 所以v也不能到 return false; }2.记录路径
//要记录路径，可以开一个数组，路径最长就是点的个数。 Node path[MAX_LEN]; int depth; //表示深度，也就是路径长度，初始为0 int main() { 将所有点都标记为新点 depth = 0; if(dfs(起点) == true) { //从0到depth，path[i]就是路径上第i步的点 for(int i = 0;i <= depth; i++) { cout<<path[i]<<endl; } } } bool dfs(v) { //边界条件 if(v为终点) { path[depth] = v; return true; } if(v是旧点) return false; 将v标记为已经访问过 path[depth] = v; //尝试把v放入到path depth++; //深度应该加1 for(与v相邻的所有点u) { if(dfs(u) == true) return true; } //如果u到不了终点 那么说明路径上v不合适 depth--; //直接将depth--即可，下一次更新path数组时直接覆盖 return false; }3.遍历所有的点（不连通也可以）
int main() { 将所有点标记为新点 while(图中能找到v是新点) { dfs(v); } } void dfs(v) { if(v是旧点) return ; 将v标记为旧点 for(v相邻的所有的点u) { dfs(u); } }题目1：城堡问题 OpenJ_Bailian - 2815
描述：
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (图 1) # = Wall | = No wall - = No wall图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分>割成mn(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
输入： 程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。
输出： 城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
样例输入：
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13样例输出：
5 9思路分析:
首先由题目可以知道，抽象为模型，一个点可以到另一个点那么这两个点之间就有一条边，那么一个房间就是一个连通子图；而这道题求得就是最大连通子图的个数，以及其中点最多的最大连通子图的顶点个数。
其次，题目中说用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。我们知道1，2,4,8的二进制表示分别是0001,0010,0100,1000.也就是说这些数字的和（有哪些墙的组合）有一个规律：相应位置上的二进制为1，那么就表示有对应的方向的墙。比如13这个数字的二进制是1101,那么就表示有西墙、东墙和南墙。那么我们用 & 就可以看是否有对应的墙。
知道哪些方向有墙后，就能遍历整个图，那么我们用染色的思想，一个联通子图就染成一个颜色(用数字表示)，最后就可以通过看有几种颜色，每种颜色有多少种来得到答案了。
AC代码
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int x,y; //x,y表示南北向，东西向的方块数 int map[55][55]; //用map存放城堡的地图 int color[55][55]; //用color数组来表示每个点是否访问过以及分组 int area,maxArea = 0; //表示当前子图的面积以及最大的面积 int num = 0; //房间数 void dfs(int i,int j) { //若已经访问过 if(color[i][j] != 0) return; area++; //该房间可走且未走过，所以面积++ color[i][j] = num; //让改点的color为num房间号，染色 //然后访问与i，j相邻的所有可以访问点 if((map[i][j] & 1) == 0) dfs(i,j-1); //西边无墙 if((map[i][j] & 2) == 0) dfs(i-1,j); //北边无墙 if((map[i][j] & 4) == 0) dfs(i,j+1); //东边无墙 if((map[i][j] & 8) == 0) dfs(i+1,j); //南边无墙 } int main() { scanf("%d %d",&x,&y); for(int i = 0;i < x; i++) for(int j = 0;j < y; j++) scanf("%d",&map[i][j]); memset(color,0,sizeof(color)); //标记所有点为新点 for(int i = 0;i < x; i++) { for(int j = 0;j < y; j++) { if(color[i][j] == 0) { /*当该点未被访问过，那么说明一定是一个新的联通子图， 房间数++；*/ num ++; area = 0; //当前房间面积设置为0 dfs(i,j); if(maxArea<area) maxArea = area; } } } //遍历完图，房间数和最大面积也就得出 printf("%d\n",num); printf("%d\n",maxArea); return 0; }题目2：踩方格 OpenJ_Bailian - 4103
描述：
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设： a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b. 走过的格子立即塌陷无法再走第二次； c. 只能向北、东、西三个方向走； 请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
输入: 允许在方格上行走的步数n(n <= 20)
输出： 计算出的方案数量
样例输入：
2样例输出：
7思路分析:
首先根据题目，我们可以得出是要我们求出第i，j个位置走n步有多少种走法，其中只能向三个方向走
然后其实这个题也是用到了深度优先搜索，首先我们的起始状态就是(X0,Y0,N),表示我们在第X0行第X0列上，还要走n步的不同走法。我们的结束状态是(Xi,Yi,0)，也就是到了某一个位置，还要走0步。我们要求得就是从初始状态到结束状态总共有多少种方法，其中每一个状态(Xi,Yi,Ni)就代表一个点。
而(Xi, Yi, Ni) = (Xi + 1, Yi, n - 1) + (Xi, Yi - 1, n - 1) + (Xi, Yi + 1, n - 1); 即从一个状态可以到其他三种状态，而该状态的值就是其他三种状态的值的和。
AC代码
#include<iostream> #include<cstdio> using namespace std; int num = 0; //方案数 //确定map的大小 因为最多一个方向连走n步(n<=20) 所以上下25，左右50(从中间开始) int map[25][50]={0}; int N; //要走多少步 int dfs(int i,int j,int n) { //边界条件 当要走的是0步时，那就是不走这一种方案 if(n == 0) return 1; map[i][j] = 1; //表示现在要访问这一个点 /*接下来是状态的转移 之前在递归函数开头判断该点是否可走 现在是可走再递归*/ int x = 0; if(map[i+1][j] == 0) x += dfs(i + 1, j, n - 1); if(map[i][j+1] == 0) x += dfs(i, j + 1, n - 1); if(map[i][j-1] == 0) x += dfs(i, j - 1, n - 1); /*把map[i][j]重新置为0,因为表示不要这一步不要访问这个点了 要退回去 让这一步变成访问其他的点*/ map[i][j] = 0; return x; } int main() { scanf("%d",&N); //表示从第0行，第25列走n步的总共走法 printf("%d",dfs(0,25,N)); return 0; }深搜最短路径+剪枝POJ1724：RODES
深搜+剪枝POJ1190：生日蛋糕
