一本通之深度搜索合集

其实比起广搜，深搜的应用范围更广泛，深搜的题目也是更经典的
所以，深搜，我来了！？！？！？！？！？！

这个题不是之前在递推中做过吗？
其实方法差不多了

#include
#include
#include
#include
#include
using namespace std;
int t;
int m,n;
int ans;
int a[100]={1};//类似于f数组，用来记录方案的个数 
void dfs(int s,int k)
{
	for(int i=a[k-1];i<=s;i++)
	{
		if(i<=m)
		{
			s-=i;//假设放苹果 
			a[k]=i;//并且记录 
			if(s==0&&k<=n) ans++;//记录答案
			else dfs(s,k+1);//否则深搜下去 
			s+=i;//回溯 
		}
	}
}
int main()
{
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		ans=0;
		cin>>m>>n;
		dfs(m,1);
		cout< 
1219 马走日 
这个题肯定又是象棋一类的
 搜索能解决的，动规不一定能解决，但是动规能解决的，搜索一定能解决
 这是我所总结的话，因为我感觉他们的联系很大
 首先这个题很简单的，我做过这个题
 深搜的题目都差不多
 
#include
#include 
#include
#include
#include
using namespace std;
int t;
int ans;
int book[100][100];
int x0,y0;
int n,m;
int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{2,1},{2,-1},{1,2},{1,-2}};
void dfs(int x,int y,int step)
{
	if(step==n*m)
	{
		ans++;
		return ;//表示搜索到头了 
	} 
	for(int i=0;i<8;i++)
	{
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx>=0&&yy>=0&&xx>t;
	while(t--)
	{
		ans=0;
		memset(book,0,sizeof(book));
		cin>>n>>m;
		cin>>x0>>y0;
		book[x0][y0]=1;
		dfs(x0,y0,1);
		cout< 
1216 红与黑 
这个题，之前听一个高二的大哥讲过
 事实证明，我做过这道题
 
#include
using namespace std;

int w, h;//方格大小     
int sx, sy;//起始位置“@”的位置       
char mp[25][25];//地图 
char c;//字符          
int ans;//答案          
int fx[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向 

//函数遍历 
void dfs(int x,int y){
    mp[x][y]='#';//将自己走过的地方标记为红色，也就是说这一步已经走过了，不可以重复走 
    ans++;//每遍历一个黑色方格就加一 
    for(int i=0;i<4;i++){//方向遍历 
        int nx=x+fx[i][0];
        int ny=y+fx[i][1];
        if(nx>=0 && nx=0 && ny>w>>h;//方格大小 
        getchar();//过滤换行符               
        if(w==0 && h==0)break;//结束判断        
        for(int i=0;i>mp[i];//输入 
        for(int i=0;i 
1318 自然数的拆分 
早就做过，懒得写一遍了
 
#include
using namespace std;
int n,sum;
int a[100]={1};
void dfs(int s,int t);
void print(int t);
int main()
{
	
	cin>>n;
	dfs(n,1);
	return 0;
}
void dfs(int s,int t)
{
	int i;
	for(i=a[t-1];i<=s;i++)
	{
		if(i 
1317 拆分问题 
也做过了，早在去年的夏令营就做过了，懒得再做了
 
#include
#include
#include
#include
int n,r;
int v[100];
using namespace std;
void dfs(int step)
{
	int i;
	if(step>r)
	{
		for(i=1;i<=r;i++)
			cout< 
1212 LETTERS 
#include
#include
#include
#include
#include 
using namespace std;
char a[28][28];
int vis[28][28];
int num[27];
bool b[27];
int f[5][3]= {{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}};
int r,s;
int maxn=0;

void dfs(int x,int y,int st)
{
    if(maxn0&&nx<=r&&ny>0&&ny<=s&&vis[nx][ny]==0&&num[a[nx][ny]-64]==0)
		{
            vis[nx][ny]=1;
            num[a[nx][ny]-64]=1;
            dfs(nx,ny,st+1);
            vis[nx][ny]=0;
            num[a[nx][ny]-64]=0;//回溯 
        }
    }
}

int main() 
{
    scanf("%d%d",&r,&s);
    for(int i=1; i<=r; i++) 
	{
        for(int j=1; j<=s; j++) 
		{
            cin>>a[i][j];
        }
    }
    num[a[1][1]-64]=1;
    vis[1][1]=1;
    dfs(1,1,1);
    cout<