dfs的模板
不知不觉开学两周了。。。 嗯。。 迷迷糊糊的看了几天的算法，尤其是深搜方面的，刷了不少的题，总觉的是时候在去巩固一下深搜的基本思路了
深搜的本质就是围绕着两方面去写代码，第一步是当前做什么？下一步是做什么？围绕着两方面可以则可以得出dfs的基本模板
void dfs(step)
{ if(判断是否到达搜索的终点)
if(判断数据是否越界)
for()
//做下一步的事
dfs(step+1)
}两道例题
凑数字
从1-9的数字中选取出不同的数字组合，使得其可以组合成口口口+口口口=口口口
这题可以用几个for循环暴力嵌套，但是搜索比起来思路更清晰
假设你 手中有 1–9号的扑克牌 将这九张扑克牌放入九个容器中 使得 口口口+口口口=口口口 成立 有多少种解法*
include<stdio.h>
int a[10]; *//放入扑克牌的箱子*
int book[10]; *//扑克牌*
int total=0; *//解法*
void dfs(int *step*)
{ int i;
if(*step*==10)
{
if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
{ total++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9] );}
return ;
}
for(int i=1;i<=9;i++) *//从第一个箱子开始 可以放入1---9号的扑克牌*
{
if(book[i]==0)
{
a[*step*]=i;
book[i]=1;
dfs(*step*+1);
book[i]=0; //用完的数字取消标记
}
}
return;
}
int main()
{ dfs(1);
printf("total=%d",total/2);
getchar();
return 0;
}走迷宫
高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。
现在给出地图：
s：代表高桥先生的家
g：代表鱼店
.：代表道路
#：代表墙壁
高桥先生不能穿过墙壁。
输入：第一行输入n(1<=n<=500),m(1<=m<=500)代表小区的长和宽，接下来n行每行m个字符，描述小区中的每个格子。
输出：如果高桥先生能到达鱼店，输出”Yes”，否则输出”No”。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N=510;
char Map[N][N]; *//定义地图*
bool jud[N][N]; *//定义地图的每个点是否可以到达*
int sx, sy;
int ex, ey;
int vis[N][N];
int n,m;
int Move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int *x*,int *y*)
{ vis[*x*][*y*]=1;
int nx,ny;
for(int i=0;i<4;i++)
{
nx=*x*+Move[i][0];
ny=*y*+Move[i][1];
if(nx<1||ny<1||nx>n||ny>m) continue;
if(Map[nx][ny]!='#'&&(vis[nx][ny]!=1))
dfs(nx,ny);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{ cin>>Map[i][j];
if(Map[i][j]=='s')
{sx=i;
sy=j;}
if(Map[i][j]=='g')
{
ex=i;
ey=j;
}
}
dfs(sx,sy);
if(vis[ex][ey]==1)
{
cout<<"yes";
}
else
{
cout<<"no";
}
}
