一、DFS简单介绍与举例理解
例：全排列
二、归纳总结：
例：
1954: 2018蓝桥杯培训-搜索专题-day 1 深度优先搜索作业题1
题目描述：
标题：方格分割
6x6的方格，沿着格子的边线剪开成两部分。 要求这两部分的形状完全相同。
如图：就是可行的分割法。 
试计算： 包括这3种分法在内，一共有多少种不同的分割方法。 注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
输入：
无
输出：
请提交该整数，不要填写任何多余的内容或说明文字。
样例输入
无
样例输出
无
#include <iostream> //方格分割，这题拿到手，绝没想到DFS； using namespace std; int book[10][10]; //标记数组； int nex[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; //方向数组 int cnt=0; void dfs(int x,int y) { if(x==0||y==0||x==6||y==6) { cnt++; return; } for(int i=0;i<4;i++) { int dx=x+nex[i][0],dy=y+nex[i][1]; if(book[dx][dy]==0) { book[dx][dy]=1; book[6-dx][6-dy]=1; dfs(dx,dy); book[dx][dy]=0; book[6-dx][6-dy]=0;//两点横坐标的平均数等于对称中心的横坐标，两点纵坐标的平均数等于对称中心的纵坐标。 } } } int main() { book[3][3]=1; //dfs起点一定要记得标记！！！，有次奇偶剪枝的题就是dfs起点未标记； dfs(3,3); cout << cnt/4 << endl; //中心对称图形; return 0; }
例：
题目描述：
X星球的一处迷宫游乐场建在某个小山坡上。 它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。 我们假设玩家是面朝上坡的方向站立，则： L表示走到左边的房间， R表示走到右边的房间， U表示走到上坡方向的房间， D表示走到下坡方向的房间。
X星球的居民有点懒，不愿意费力思考。 他们更喜欢玩运气类的游戏。这个游戏也是如此！
开始的时候，直升机把100名玩家放入一个个小房间内。 玩家一定要按照地上的字母移动。
迷宫地图如下：
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
请你计算一下，最后，有多少玩家会走出迷宫? 而不是在里边兜圈子。
如果你还没明白游戏规则，可以参看一个简化的4x4迷宫的解说图：
输入：
无
输出：
请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。
#include <iostream> #include <cstring> using namespace std; //int nex[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; char maze[11][11]={ {"UDDLUULRUL"},{"UURLLLRRRU"},{"RRUURLDLRD"},{"RUDDDDUUUU"},{"URUDLLRRUU"}, {"DURLRLDLRL"},{"ULLURLLRDU"},{"RDLULLRDDD"},{"UUDDUDUDLL"},{"ULRDLUURRR"} }; int vis[13][13]={0}; int cnt=0; void dfs(int x,int y) { int dx=x,dy=y; switch(maze[x][y]) { case 'L': dy--; break; //一开始忘记写break了还一直WA不知道原因！！ case 'R': dy++; break; case 'U': dx--; //向上和向下反了一开始！！，仔细点 break; case 'D': dx++; break; } if(dx==-1||dy==-1||dx==10||dy==10) //找到边界出去了； { cnt++; //一开始敲成x和y了，结果越界程序不能运行； return; } if(vis[dx][dy]==0) { vis[dx][dy]=1; dfs(dx,dy); // cout << cnt << endl; } } int main() { for(int i=0;i<10;i++) { for(int j=0;j<10;j++) { memset(vis,0,sizeof(vis)); vis[i][j]=1; //遍历迷宫的每一个点计算，调用dfs，计算其最后能否出去; dfs(i,j); } } cout << cnt << endl; return 0; } /* UDDLUULRUL UURLLLRRRU RRUURLDLRD RUDDDDUUUU URUDLLRRUU DURLRLDLRL ULLURLLRDU RDLULLRDDD UUDDUDUDLL ULRDLUURRR*/
UVA291 The House Of Santa Claus
