C++:第十二讲DFS深搜(二)

发布时间:2024年01月05日

前言

今天带着大家学习一下DFS的各类题目,如果想了解一些基础,可以看:C++:第十一讲DFS深搜-CSDN博客

DFS回顾

温故而知新,让我们一起把上节课的内容复习一遍吧!

搜索算法,就是利用计算机的高性能,对问题的“状态空间”进行枚举,穷举出一个问题的全部或者部分可能的情况,找到最优解或者统计合法解的个数。 ? ? ? ?在搜索算法中,深度优先搜索算法(Depth First Search,DFS,简称深搜),常常指利用递归函数方便地实现暴力枚举的算法,也称为“回溯法”。通过递归函数,我们可以逐层地枚举每一种可能,从而实现枚举所有可能的“状态”。 ? ? ? 搜索算法是一些高级算法的基础,而搜索算法可以在很多问题中解决数据范围较小的部分。掌握正确的写搜索算法,对后续高级算法的学习和理解有着一定的帮助。

本节课将介绍数的拆分问题、N皇后问题、迷宫问题。

例题P2404 自然数的拆分问题

题目描述

任何一个大于?11?的自然数n,总可以拆分成若干个小于?n?的自然数之和。现在给你一个自然数?n,要求你求出n?的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。

输入格式

输入:待拆分的自然数?n。

输出格式

输出:若干数的加法式子。

输入?

7

输出

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

数据保证,2≤n≤8。

解题思路

对于如本题所示,n的数据范围足够小(30以内),我们可以很容易估算
出,当将n拆分成若干个不同正整数的和时,其总的方案数并不会很大。因此,
可以尝试使用DFS深度优先搜索算法将方案数一一搜索出来。
根据题意,首先,假设将n拆分成m个正整数的和,即有n=a1+a2+...an,
且满足a1<a2<...<am。然后,依次枚举a1,a2,a3...,在枚举过程中保证

ai+1>ai

AC:

#include<bits/stdc++.h>
using namespace std;
int n,a[10];
void dfs(int he,int c,int qs){
	if(he==n){
		for(int i=1;i<=c-2;i++){
			cout<<a[i]<<'+';
		}//输出。
		cout<<a[c-1]<<endl;
		return ;
	}
	if(he>n) return;//过头返回。
	for(int i=qs;i<=n-1;i++){
		a[c]=i;//记录输出。
		dfs(he+i,c+1,i);
		a[c]=0;//改回原来的0;
	}
}
int main(){
	cin>>n;
	dfs(0,1,1);
	return 0;
}

N皇后问题 (有修改)

题目描述

这题是著名的?N?皇后问题。

输入格式

第一行有一个?N。接下来有?N?行?N?列描述一个棋盘,Q?表示可放,.表示不可放。

输出格式

输出方案。

输入 #1

4

输出 #1

.Q..
...Q
Q...
..Q.
 
..Q.
Q...
...Q
.Q..
 

说明/提示

140<n≤14

解题思路

n皇后问题是指将?n个皇后放在 n×n?的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

显然这道题可以直接暴力搜索。不会的自行搜索DFS。但是只能得60分。

但是TLE四个点。为什么呢?看到dfs函数中的for循环一行。其中有很多方案是不可能的,但是这样写的话必须一个一个判断是否可以落子。导致超时。如何改进呢?

这里我们可以用位运算进行优化。我们用整形中的一个bit表示当前位置是否可以落子。对于左右斜线,竖线各保存一个副本。求并集(C++中的&运算)可以得到哪里可以落子。再用lowbit运算得到第一个可以落子的位置,这样只需要判断是不是*字符就行了。

具体而言,我们用函数 DFS。

大致思路:

1.用一个二进制数表示一行的摆放情况,0表示可以放皇后,1表示不可以放皇后,别忘了皇后上下左右和两条斜对角线都吃得了。

2.用sp[i]表示第i行的摆放情况,.表示不可以放皇后,但是因为棋盘是从左向右的,而二进制数是从右向左的,所以sp[i]∣=(1<<(n?j))表示将第i行从左到右第j个格子置为不可放皇后。

每行需要恰好放一个皇后。不妨用数组 记录第 行的皇后的列坐标。
思路:逐行放置皇后,要保证皇后的"列坐标","行列坐标和","行列坐标差"互不相同。
用dfs实现,放置了皇后 ,用三个数组分别将 "标记"。?

?AC:

#include<bits/stdc++.h>
using namespace std;
int a[30],b[30],c[30],p[30],n;
void print(){
??for (int i=0;i<n;i++){
????for (int j=0;j<n;j++) if (p[i]==j) cout << "Q"; else cout << ".";
????cout << endl;
?}
??cout << endl;
}
void dfs(int x){
??if (x==n){
????print(); //打印方案
????return;
?}
??for (int i=0;i<n;i++){
????if (!a[i]&&!b[i+x]&&!c[i+n-x]){
??????a[i]=1; b[i+x]=1; c[i+n-x]=1; //分别标记"列坐标”,“行列坐标和”,“行列坐标
差”
??????p[x]=i; dfs(x+1);
??????a[i]=0; b[i+x]=0; c[i+n-x]=0; //撤销
???}
?}
}
int main(){
??cin >> n;
??dfs(0);
}

洛谷P1363 幻象迷宫

题目背景

(喵星人 LHX 和 WD 同心协力击退了汪星人的入侵,不幸的是,汪星人撤退之前给它们制造了一片幻象迷宫。)

WD:呜呜,肿么办啊……

LHX:momo...我们一定能走出去的!

WD:嗯,+U,+U!

题目描述

幻象迷宫可以认为是无限大的,不过它由若干个N×M?的矩阵重复组成。矩阵中有的地方是道路,用?.表示;有的地方是墙,用?#表示。LHX 和 WD 所在的位置用?S?表示。也就是对于迷宫中的一个点(x,y),如果 (xmodn,ymodm)?是?..?或者?SS,那么这个地方是道路;如果 (xmodn,ymodm)?是##,那么这个地方是墙。LHX 和 WD 可以向上下左右四个方向移动,当然不能移动到墙上。

请你告诉 LHX 和 WD,它们能否走出幻象迷宫(如果它们能走到距离起点无限远处,就认为能走出去)。如果不能的话,LHX 就只好启动城堡的毁灭程序了……当然不到万不得已,他不想这么做。

输入格式

输入包含多组数据,以 EOF 结尾。

每组数据的第一行是两个整数 N,M。

接下来是一个 N×M?的字符矩阵,表示迷宫里 (0,0)?到?(n?1,m?1)?这个矩阵单元。

输出格式

对于每组数据,输出一个字符串,Yes?或者?No

输入输出样例

输入 #1

5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##

输出 #1

Yes
No

解题思路

当你在其中一个迷宫走到了(x,y)这个点,在另一个迷宫也走到了(x,y)这个点,你就走出去了。

所以这道题只需要在普通bfs的基础上,改变book数组的含义。

以前book数组表示(x,y)这个点是否被访问过,现在book数组有了双重含义,还表示了这个点是在哪一个迷宫中被访问的。

所以我们记录当前的实际坐标(x,y),和在原迷宫中映射的坐标(tx,ty)=(x%n,y%m)。

对于实际坐标(x,y),建立一个hash值f(x,y)。

当拓展到一个点时,如果(tx,ty)这个点是障碍,直接continue。

如果f(x,y)==book[tx][ty],就表示这个点曾经来过,continue。

如果f(x,y)!=book[tx][ty]&&book[tx][ty]!=0,就表示曾经在另一个迷宫中来过这个点,走出去了。

如果book[tx][ty]==0,表示这个点没有走过,继续bfs。

f(x,y)这个函数看心情随便写就好啦,但是要注意不要和其他的f(x,y)重复。

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1500 + 1;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int n, m;
int st_x, st_y;
int vis[MAXN][MAXN][3];
bool fl, a[MAXN][MAXN];
char ch;
void dfs(int x, int y, int lx, int ly) {
	if(fl) return;
    if(vis[x][y][0] && (vis[x][y][1]!=lx || vis[x][y][2]!=ly)) {
         fl = 1;
         return;
     }
     vis[x][y][1] = lx, vis[x][y][2] = ly, vis[x][y][0] = 1;
     for(int i=0; i<4; ++i) {
         int xx = (x + dx[i] + n) % n, yy = (y + dy[i] + m) % m;
         int lxx = lx + dx[i], lyy = ly + dy[i];
         if(!a[xx][yy]) {
             if(vis[xx][yy][1]!=lxx || vis[xx][yy][2]!=lyy || !vis[xx][yy][0])
                dfs(xx, yy, lxx, lyy);         }
    }
}
	int main() {
    ios::sync_with_stdio(false);
    while(cin >> n >> m) {
        fl = 0;
        memset(a, 0, sizeof(a));
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j) {                 cin >> ch;
            	if(ch == '#') a[i][j] = 1;
                 	if(ch == 'S') st_x = i, st_y = j;
             }
        dfs(st_x, st_y, st_x, st_y);
        if(fl) puts("Yes");
        else puts("No");
    }
    return 0; 
}

拓展题 ——洛谷P1236 算24点

链接——算24点 - 洛谷
?

题目描述

几十年前全世界就流行一种数字游戏,至今仍有人乐此不疲.在中国我们把这种游戏称为“算24点”。您作为游戏者将得到?4?个 1~9?之间的自然数作为操作数,而您的任务是对这?44?个操作数进行适当的算术运算,要求运算结果等于?24。

您可以使用的运算只有:+,-,*,/,您还可以使用?()来改变运算顺序。注意:所有的中间结果须是整数,所以一些除法运算是不允许的(例如,(2?×2)/4?是合法的,2×(2/4)?是不合法的)。下面我们给出一个游戏的具体例子:

若给出的?4个操作数是:1?、?2?、?3、??7,则一种可能的解答是?1+2+3?×7=24。

输入格式

只有一行,四个1到9之间的自然数。

输出格式

如果有解的话,只要输出一个解。输出的是三行数据,分别表示运算的步骤。

其中第一行是输入的两个数和一个运算符和运算后的结果;

第二行是第一行的结果和一个输入的数据、运算符、运算后的结果,或者是另外两个数的输出结果;

第三行是前面的结果第二行的结果或者剩下的一个数字、运算符和?=24=24。如果两个操作数有大小的话则先输出大的。

如果没有解则输出?No answer!

如果有多重合法解,输出任意一种即可。

注:所有运算结果均为正整数。

输入 #1

1 2 3 7

输出 #1

2+1=3
7*3=21
21+3=24

解题思路

本题是经典的搜索问题。
从起点出发,我们可以枚举每一步是向哪个方向走(上/下/左/右)。
函数 表示当前走到的格子是 。到达 后,可以递归地调用dfs(x-
1,y),dfs(x+1,y),dfs(x,y-1),dfs(x,y+1)。
题目要求每个格子只能走一次,所以在dfs过程中,每次经过一个点,将这个点标记;每次递归返
回时,将标记撤销。
dfs的终止条件是走到终点。

AC:

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty,t,ans;
bool f[7][7];
void dfs(int x,int y){
??if (x==tx&&y==ty){
????ans++; //走到终点,终止
????return;
?}
??f[x][y]=1; //标记(x,y)为已走过
??if (!f[x-1][y]) dfs(x-1,y); //试图向四个方向走
??if (!f[x+1][y]) dfs(x+1,y);
??if (!f[x][y-1]) dfs(x,y-1);
??if (!f[x][y+1]) dfs(x,y+1);
??f[x][y]=0; //撤销标记
}
int main(){
??memset(f,1,sizeof(f));
??cin >> n >> m >> t;
??for (int i=1;i<=n;i++)
????for (int j=1;j<=m;j++)
??????f[i][j]=0;
??cin >> sx >> sy >> tx >> ty;
??for (int i=0;i<t;i++){
????int x,y; cin >> x >> y;
????f[x][y]=1;
?}
??dfs(sx,sy);
??cout << ans << endl;
  return 0;
}

结尾

本篇文章共5434字,如果你能支持一下我,我十分感谢!!!

如果有人想在洛谷上做题,可以点下方链接:

https://www.luogu.com.cn/

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

C++小游戏:

C++:自创小游戏-CSDN博客

DFS深搜;

C++:第十一讲DFS深搜-CSDN博客

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!

文章来源:https://blog.csdn.net/2301_81328824/article/details/135412340
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。