深搜（洛谷普及）

最新推荐文章于 2024-07-07 22:24:25 发布

coder370

最新推荐文章于 2024-07-07 22:24:25 发布

阅读量258

点赞数

分类专栏：搜索

本文链接：https://blog.csdn.net/coder370/article/details/102529201

版权

搜索专栏收录该内容

5 篇文章

订阅专栏

本文介绍了几个使用深度搜索（深搜）解决的编程题目，包括八皇后问题、迷宫求解、单词接龙的预处理与搜索、以及单词方阵的构建。通过实例详细解析了深搜在不同场景下的常规操作和注意事项，如单词接龙中的后缀前缀匹配，以及单词方阵中确保正确路径的搜索策略。此外，还提到了一个与二叉树相关的加分问题，利用区间DP和深搜找到最大加分值的策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

**
P1219 八皇后**

#include <cstdio>
const int N = 15 ;  
int n , queen[N] ;
int ans = 0 ;
int flag[3][N*2] ; 
void dfs(int k){
    if (k == n){
		if (ans < 3){
			for (int i = 0 ; i < n-1 ; i ++)
				printf ("%d ",queen[i]+1);
			printf ("%d\n",queen[n-1]+1);
		}
        ans ++ ;
    }     
   	for (int j = 0 ; j < n ; ++ j){
   		if (!flag[0][j] && !flag[1][k+j] && !flag[2][k-j+n]){
			flag[0][j] = 1 , flag[1][k+j] = 1 , flag[2][k-j+n] = 1 ;  
			queen[k] = j ; 
			dfs(k+1) ;  
			//深搜结束恢复深搜前的状态 
			flag[0][j] = 0 , flag[1][k+j] = 0 , flag[2][k-j+n] = 0 ;  
		}	
	}
}
int main(){
    scanf ("%d",&n);
    dfs(0);
    printf ("%d\n",ans);
    return 0  ;
}

P1605 迷宫
普通的搜索题，常规操作

#include <cstdio>
const int N = 8 ; 
int n , m , t , ans ;
int maze[N][N] ; 
int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}} ; 
int a , b , c , d ;
void dfs(int x1 , int y1 , int x2 , int y2){
	int x , y ;
	if (x1 == x2 && y1 == y2){
		ans ++ ; //到达终点方案加一
		return ; 
	} 
	for (int i = 0 ; i < 4 ; ++i){
		x = x1 + dir[i][0] ; 
		y = y1 + dir[i][1] ; 
		if (x>=1&&x<=n&&y>=1&&y<=m && !maze[x][y]){
			maze[x][y] = 1 ; 
			dfs(x,y,x2,y2) ; 
			maze[x][y] = 0 ;
		}   
	}
}
int main(){
	scanf ("%d%d%d",&n,&m,&t) ;
	scanf ("%d%d",&a,&b) ;
	scanf ("%d%d",&c,&d) ;  
	int x , y ;
	for (int i = 1 ; i <= t ; ++i){
		scanf ("%d%d",&x,&y) ; 
		maze[x][y] = 1 ; 
	}
	maze[a][b] = 1 ; 
	dfs(a,b,c,d) ; 
	printf ("%d\n",ans) ; 
	return 0 ;  
}

P1019 单词接龙
先预处理单词，num[i][j]表示第i个单词的后缀与第j个单词的前缀的最小重叠部分，然后常规的深搜了。

#include <cstdio>
#include <cstring>
#include <string.h>
#include <algorithm>
using namespace std ; 
const int N = 30 ; 
char word[N][N] ; 
int num[N][N] ; //找出x单词的后缀和y的前缀的最小重叠数 
int vis[N] ;  //记录使用了几次 
int n , ans , con ; //ans记录最大长度，con记录当前长度 

void init(int x , int y){	//找出x单词的后缀和y的前缀的最小重叠数 
	int xlen = strlen(word[x]) , ylen = strlen(word[y]) ; 
	int count = 0 , k ; 
	for (int i = xlen-1 ; i >= 0 ; -- i){
		int j = 0 ; 
		if (word[y][j] == word[x][i]){
			k = i ;  
			while(k < xlen && j < ylen && word[x][k] == word[y][j]){
				count ++ ; 
				++ j , ++ k ; 
			}
			break ; 
		}
	}
	if (count == ylen)	num[x][y] = -1 ; //如果重叠数为y的长度 则说明x包含y 记录num为-1（不可使用） 
	else{
		if (k <= xlen-1){	//若k不是x的最后一个字母，则x后缀 与 y前缀无重叠部分 
			num[x][y] = 0 ;  
		}
		else {
			num[x][y] = count ;
		}	
	} 
}
void dfs(int x){
	int flag = false ; 
	for (int i = 0 ; i < n ; ++ i){
		if (num[x][i] > 0 && vis[i] < 2){
			flag = true ; 
			vis[i] ++ ; 
			con += strlen(word[i]) - num[x][i] ; 
			dfs(i) ;
			//恢复状态 
			vis[i] -- ; 
			con -= strlen(word[i])- num[x][i] ; 
		}
	}
	if (flag == false){	//若没有匹配的单词即可更新ans和返回 
		ans = max(ans,con) ;
		return ;  
	}
	
}
int main(){
	char ch ; 
	scanf ("%d",&n) ;
	for (int i = 0 ; i < n ; ++ i)
		scanf ("%s",word[i]) ;
	scanf ("%s",&ch) ; 
	for (int i = 0 ; i < n ; ++i)
		for (int j = 0 ; j < n ; ++ j){
			init(i,j) ;   
		} 
	
	for (int i = 0 ; i < n ; ++ i){
		if (word[i][0] == ch){
			vis[i] ++ ; 
			con = strlen(word[i]) ; 
			dfs(i) ;
			vis[i] -- ; 
		} 
	} 
	printf ("%d\n",ans) ; 
	return 0 ; 
}

p1101 单词方阵

先搜索到y为起点然后向八个方向搜索i，若搜索到i则确定该反向搜索剩余的字符串，用ans数组存放搜索到字符串的哪一位字符，要注意now的确定在dfs之后，只有最后一个字符确定了才能赋值前面的ans数组，所以在赋值前判断dfs即可。

#include <cstdio>
const int N = 105 ; 
char maze[N][N] ; 
int ans[N][N] ; 
char str[10] = " yizhong" ; 
int n , now ; 
int dir[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{-1,-1},{1,1},{-1,1},{1,-1}} ; //八个方向 
bool dfs(int x , int y , int now , int d){	//坐标，当前字符，方向 
	x = x + dir[d][0] ; 
	y = y + dir[d][1] ; 
	if (maze[x][y] == str[now]){	//当最后一个字符也对了即可返回 
		if (now == 7){
			ans[x][y] = 7 ;
			return true ; 
		}
		if (dfs(x,y,now+1,d)){
			ans[x][y] = now ;  
		} 
		else	return false ; 
	}
	else return false ; 
}
int main(){
	scanf ("%d",&n) ;
	for (int i = 0 ; i < n ; ++ i)	scanf ("%s",maze[i]) ;
	for (int i = 0 ; i < n ; ++ i){
		for (int j = 0 ; j < n ; ++ j){
			if (maze[i][j] == 'y'){
				for (int k = 0 ; k < 8 ; ++ k){
					int x = i + dir[k][0] ; 
					int y = j + dir[k][1] ; 
					if (x>=0&&x<n && y>=0&&y<n && maze[x][y]=='i'){
						if(dfs(x,y,3,k)){
							ans[x][y] = 2 , ans[i][j] = 1 ; 
						}
					}
				}
			}
		}
	}
	
	for (int i = 0 ; i < n ; ++ i){
		for (int j = 0 ; j < n ; ++ j){
			if (ans[i][j] == 0)		printf ("*") ;
			else	printf ("%c",str[ans[i][j]]) ; 
		}
		printf ("\n") ;
	}
	return 0 ;
}

**
P1040 加分二叉树**
区间dp，f[i][j]表示i到j之间的最大加分值，用root[i][j]记录区间i和j最大加分值的根节点。

#include <cstdio>
typedef long long ll ; 
const int N = 35 ; 
ll f[N][N] ;
int root[N][N] ; 
void print(ll l , ll r){
	if (l>r)	return ; 
	if (l == r)	{
		printf ("%d ",l) ; 
		return ; 
	}
	int t = root[l][r] ; 
	printf ("%d ",t) ;	//输出根节点 
	print(l,t-1) ; //输出左子树 
	print(t+1,r) ; //输出右子树  
} 
int main(){
	int n ; 
	scanf ("%d",&n) ;
	for (int i = 1 ; i <= n ; ++ i){
		scanf("%lld",&f[i][i]) ;
		f[i][i-1] = 1 ; //子叶的左子树为空树，权值为 1 
	} 	
	for (int len = 1 ; len <= n ; ++len){
		for (int l = 1 ; l <= n-len ; ++ l){
			int r = l + len ;
			for (int k = l ; k <= r ; ++ k){ //遍历找出以k为根节点的最大值 
				if (f[l][r] < f[l][k-1]*f[k+1][r]+f[k][k]){
					f[l][r] = f[l][k-1]*f[k+1][r]+f[k][k] ; 
					root[l][r] = k ; //记录最大值的根节点 
				} 
			}
		}
	} 
	printf("%d\n",f[1][n]) ; 
	print(1,n) ;	
	return 0 ; 
}