DFS模板
题型分类：
们可以将DFS题分为两大类：
1 . 地图型：这种题型将地图输入，要求完成一定的任务。因为地图的存在。使得题意清楚形象化，容易理清搜索思路。
AOJ 869-迷宫(遍历地图，四向搜索)
HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)
HDU 1045-Fire Net(check函数，回溯)
HDU 1010-Tempter of the Bone(奇偶剪枝，回溯)
2 . 数据型：这种题型没有给定地图，一般是一串数字或字母，要求按照一定的任务解题。相对于地图型，这种题型较为抽象，需要在数据中进行搜索。数据以数组的形式存储，那么只要将数组也当作一张图来进行搜索就可以了。
HDU 1016-Prime Ring Problem(回溯、素数筛)
HDU 1258-Sum It Up(双重DFS递归，去重技巧)
HDU 1015-Safecraker(回溯，字符处理)
HDU 2676-Sudoku(抽象，回溯)
核心思想：
void dfs()//参数用来表示状态
{ if(到达终点状态) { ...//根据题意添加
return; } if(越界或者是不合法状态) return; if(特殊状态)//剪枝
return ; for(扩展方式) { if(扩展方式所达到状态合法) { 修改操作;//根据题意来添加
标记； dfs（）； (还原标记)； //是否还原标记根据题意 //如果加上（还原标记）就是 回溯法
} } }
迷宫（一）
一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。
看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。
输入格式
第一行输入两个整数 n 和 m，表示这是一个n×m 的迷宫。
接下来的输入一个 n 行m 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。
输出格式
输出一个字符串，如果蒜头君可以逃出迷宫输出"yes”，否则输出"no”。
数据范围
1≤n,m≤10。
样例输入1
3 4
S**.
..*.
***T
样例输出1
no
样例输入2
3 4
S**.
….
***T
样例输出2
Yes
include<iostream> include<bits/stdc++.h>
using namespace std; int n,m; char maps[15][15]; int vis[15][15]; int flag=0; int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; //判断路是否能走
bool check(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m&&maps[x][y]!='*'&&vis[x][y]==0; } void dfs(int x,int y){ //终点就退出
if(maps[x][y]=='T'){ flag=1; return ; } if(!check(x,y)) return ; vis[x][y]=1; for(int i=0;i<4;i++){ int newx=x+dir[i][0]; int newy=y+dir[i][1]; dfs(newx,newy); } return ; } int main() { int start,starty; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>maps[i][j]; if(maps[i][j]=='S'){ start=i; starty=j; } } } dfs(start,starty); if(flag==1) cout<<"yes"<<endl; else cout<<"no"<<endl; }
hdu 1035 Robot Motion
问题描述
机器人已被编程为遵循其路径中的指令。网格中放置了机器人下一步移动方向的说明。可能的指令为
N北（在页面上方）
S南（在页面下方）
E东（在页面右侧）
W西（在页面左侧）
例如，假设机器人从北（顶部）启动网格1的一侧），并向南（向下）开始。显示了机器人遵循的路径。机器人在离开网格之前会先通过网格中的10条指令。
比较Grid 2中发生的情况，机器人仅执行3条指令一次，然后通过8条指令开始循环，并且永不退出。
您将编写一个程序，该程序确定机器人离开网格需要多长时间或机器人如何循环。
输入值
将有一个或多个网格供机器人导航。每个数据的格式如下。在第一行上，三个整数用空格隔开：网格中的行数，网格中的列数以及机器人从北方进入的列数。
可能的输入列从左侧的一开始编号。然后出现方向指示的行。每个网格将具有至少一个且最多10个行和列的指令。指令行仅包含字符N，S，E或W，没有空格。
输入的结尾由包含0 0 0的行指示。
输出量
对于输入中的每个网格，只有一行输出。机器人要么遵循一定数量的指令，然后从四个侧面中的任一侧退出网格，要么机器人一次遵循一定数量位置上的指令，
然后重复遵循一定数量位置上的指令。下面的示例输入对应于上面的两个网格，并说明了两种输出形式。单词” step"总是紧随其后的是”（s）“，无论之前的数字是否为1。
样本输入
3 6 5 NEESWE WWWESS SNWWWW 4 5 1 SESWE EESNW NWEEN EWSEN 0 0
样本输出
10个步骤可在8个步骤的循环之前退出3个步骤
include<iostream> include<bits/stdc++.h>
using namespace std; char maps[15][15]; int sum,m,n,s,flag,mark,mark_x,mark_y,vis[15][15]; void dfs(int x,int y,int ant){ if(x<0||y<0||x==m||y==n){//如果出界 就证明能够出去了
flag=1; mark_x=x,mark_y=y; mark=ant; return ; } vis[x][y]=ant+1; if(maps[x][y]=='W'&&!sum&&!flag) dfs(x,y-1,++ant); if(maps[x][y]=='E'&&!sum&&!flag) dfs(x,y+1,++ant); if(maps[x][y]=='N'&&!sum&&!flag) dfs(x-1,y,++ant); if(maps[x][y]=='S'&&!sum&&!flag) dfs(x+1,y,++ant); } int main(){ while(true) { cin>>m>>n; if(m==0||n==0) break; cin>>s; for(int i=0;i<m;i++) cin>>maps[i]; sum=flag=0; memset(vis,0,sizeof(vis)); dfs(0,s-1,0); if(!flag) cout<<sum<<" step(s) to exit"<<endl; else cout<<vis[mark_x][mark_y]-1<<" step(s) before a loop of "<<mark-vis[mark_x][mark_y]+1<<" step(s)"<<endl; } }
Tempter of the Bone
小狗在一个古老的迷宫中发现了一根骨头，这使他非常着迷。但是，当他捡起它时，迷宫开始摇晃，小狗可以感觉到地面下沉。他意识到骨头是一个陷阱，
他拼命试图摆脱这个迷宫。迷宫是一个矩形，大小为N×M。迷宫中有一扇门。刚开始时，门是关闭的，它将在第T秒打开一小段时间（少于1秒）。
因此，小狗必须在第T秒精确到达门。每秒钟，他可以将一个块移动到上，下，左和右相邻的块之一。一旦他进入一个街区，该街区的地面将开始下沉并在下一秒消失。
他不能在一个街区停留超过一秒钟，也不能搬到一个拜访的街区。可怜的小狗可以生存吗？请帮助他。
输入值
输入包含多个测试用例。每个测试用例的第一行包含三个整数N，M和T（1 'X': a block of wall, which the doggie cannot enter; 'S': the start point of the doggie; 'D': the Door; or '.': an empty block. 输入以三个0终止。该测试用例将不被处理。 输出 对于每个测试用例，如果小狗可以存活，则在一行中打印"YES”，否则打印为"NO”。 样例输入： 4 4 5 S.X. ..X. ..XD …. 3 4 5 S.X. ..X. …D 0 0 0 样例输出： NO YES 奇偶剪枝 把矩阵看成如下形式： 所以当遇到从 0 走向 0 但是要求时间是奇数的或者 从 1 走向 0 但是要求时间是偶数的，都可以直接判断不可达！ HDU 1016-Prime Ring Problem 原文创作：希望每天涨粉 原文链接：https://www.cnblogs.com/BlairGrowing/p/14087982.html
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从为 0 的格子走一步，必然走向为 1 的格子 。
从为 1 的格子走一步，必然走向为 0 的格子 。
即：
从 0 走向 1 必然是奇数步，从 0 走向 0 必然是偶数步。
include<iostream> include<bits/stdc++.h>
using namespace std; int n,m,t,escape; int dx,dy,sx,sy; char maps[15][15]; int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //上下左右4个方向
void dfs(int sx,int sy,int cnt){ int tmp; //不满足要求超过地图范围
if(sx>n||sx<1||sy>m||sy>m||sy<1) //完成条件
if(sx==dx&&sy==dy&&cnt==t) if(escape) return; //T−k−f<0
tmp=(t-cnt)-abs(sx-dx)-abs(sy-dy); if(tmp<0||tmp&1)return; for(int i=0; i<4; i++ ){ int newx = sx+dir[i][0]; int newy = sy+dir[i][1]; if( maps[newx ][ newy ] != 'X'){ maps[ newx ][ newy ] = 'X'; dfs(newx, newy, cnt+1); maps[ newx ][newy ] = '.'; } } return; } int main(){ while (scanf("%d %d %d",&n,&m,&t)&&(m+n+t)){ int wall=0; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cin>>maps[i][j]; if(maps[i][j]=='S') { sx=i; sy=j; } else if( maps[i][j]=='D' ) { dx=i; dy=j; } else if( maps[i][j]=='X' ) wall++; } } if( n*m-wall <= t ){ cout << "NO" << endl; continue; } escape = 0; maps[sx][sy] = 'X'; dfs(sx,sy,0); if( escape ) cout << "YES" << endl; else cout << "NO" << endl; } }
include<iostream> include<bits/stdc++.h>
using namespace std; int n; int a[123],used[123]; int ok(int n){ int i; for(i=2;i<n;i++){ if(n%i==0) return 0; } return 1;//素数
cout<<"1"; for(j=1;j<n;j++) cout<<" "<<a[j]; //构造够n个了 输出数组。
cout<<endl; return ; } } for(i=2;i<=n;i++){ if(used[i]==0&&ok(i+a[x-1])==1) { //加上判断和是不是素数
a[x]=i; used[i]=1; //标记使用了
dfs(x+1); //对第x+1个进行构造
used[i]=0; //标记复原
} } return ; } int main(){ int cas=1; while(scanf("%d",&n)!=-1){ memset(used,0,sizeof(used)); // 赋值都没被使用过。
used[1]=1; a[0]=1; printf("Case %d:\n",cas++); dfs(1); //从第1个数开始构造，因为以1开始
cout<<endl; } return 0; }
