搜索算法--DFS+BFS

, ,

虽然DFS和BDFS都是搜索方法，但是在不同的问题中两者的效率还是会有差别的。
dfs实现的方式是递归或者非递归，但是其本质还是栈。bfs的本质则是队列。
本质不同，他们的搜索方式必然是不同的，dfs是在其中可选项中选择一个，然后再以其再递归如果不满足了就回溯。
而bfs就不同，bfs是选择一个元素，其元素的周围的可选项全部入队，然后出队首元素，出对的元素的周围可选项再全部入队，如此。
DFS类比于撞南墙（递归），撞到头不好走了就返回（回溯）；BFS就相当于水面上的涟漪，一圈一圈的扩散。
具体概念上的异同点可以查阅资料，下面举例几道题感受一下：

首先看一道经典例题：八皇后问题。
题目链接
对于要求一个棋子，其对应的所在行，所在列，所在两个对角线都不能有其他的棋子存在。

那么b[j]==0即为搜在列没有棋子。
c[i+j]==0代表其左下到右上的斜对角线上没有棋子，因为你会发现，i+j相同，即代表行+列的和相同，满足这样的情况，就是同一对角线上的棋子，且是左下到右上的斜对角线。
d[i-j+n]==0代表的是左上到右下的斜对角线的棋子们。i-j相同，即行-列的差相同，就是同一从左上到右下的斜对角线。因为i-j会有小于0的情况，所以，要+n。

程序的思想是：从第一行开始，对每一行的每一个列递归查找。如果满足条件就标记此处，在此下棋。如果下的棋子的个数达到n，就按条件输出，如果没有达到，就递归搜索下一行。如果这一行的所有列都搜索过了，且没有满足条件的地方，那么就出递归，消除上一行中下棋的地方，重新再这一行中的下面没有寻找的列中找到满足下棋的地方，如果找到就向下递归，如果这行也没有找到，就回溯到上一行，取消掉这一行中所下的棋子。
如此过程即可。
这是一个典型的深度优先遍历的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;

int a[1000],b[1000],c[1000],d[1000];
//a数组存行，b存列，c存左下到右上的对角线，d存右下到左上的对角线

int n,s;

void shuchu(){
	int i;
	s++;
	if(s<=3){
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" ";//按要求将行输出
		}
		cout<<endl;
	}
}

int search(int i){//i 行
	int j;//j 列
	for(j=1;j<=n;j++){
		if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0){//如果这个行的j列，两个写对角线都没有棋子
			a[i]=j;//那么就将这个棋子下到这，按题目要求，将j列写进去这个数组中
			b[j]=1;//此行标记为已经下了棋子了
			c[i+j]=1;//同上，只是是对角线
			d[i-j+n]=1;//同上
			if(i==n)	shuchu();//满足条件输出
			else	search(i+1);//递归
			b[j]=0;//递归口出来，要消除他们的标记，回溯
			c[i+j]=0;
			d[i-j+n]=0;
		}
	}
}
int main(){
	cin>>n;
	search(1);
	cout<<s<<endl;
	return 0;
}

接着看一道题：单词方阵
题目链接

解题思路：首先先要找到一个字符串是’y’，然后以这个字符为循环起点，分别对这个点的八个不同的方向去循环。选择一个方向，循环这个方向上的所有字符串，如果所有的字符串都和所求字符串相同，就将这个方向保存在ans数组种，如果字符串有一个不同或者越界，就至标记flag=0,跳出字符串的循环，开始下一个方向的循环。

其实这题不太算严谨的DFS，只能叫循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<string>
using namespace std;

const int maxn=110;
const int dx[]={1,1,1,0,0,-1,-1,-1};//方向数组
const int dy[]={1,0,-1,1,-1,0,1,-1};
const string cmp="yizhong";

char a[maxn][maxn],ans[maxn][maxn];
int n;

void dfs(int x,int y){//从这个点的不同的方向遍历
    for(int i=0;i<8;i++){//这里循环是，八个方向的循环
        int flag=1;
        for(int j=1;j<=6;j++){//这里循环，是字符串的循环，因为先找到了字符串的开头，
				//所以循环次数要字符串长度-1
            int xx=x+j*dx[i];//新的方向
            int yy=y+j*dy[i];
            if(xx<1||xx>n||yy<1||yy>n){//越界
                flag=0;
                break;
            }
            if(cmp[j]!=a[xx][yy]){//有一个字符不相同，就break
                flag=0;
                break;
            }
        }
        if(flag==0) continue;//如果flag==0，就继续循环下一个方向
        for(int j=0;j<=6;j++){//将满足条件的路径用ans数组保存下来
            int xx=x+j*dx[i];
            int yy=y+j*dy[i];
            ans[xx][yy]=a[xx][yy]; 
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];//输入模块
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]=='y')    dfs(i,j);//如果找到了开头的字母y，
			//那么就从此位置开始深度遍历
        }
    }
    for(int i=1;i<=n;i++){//输出
        for(int j=1;j<=n;j++){
            if(ans[i][j]==0)    ans[i][j]='*';
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}

再看一个题：迷宫
题目链接

这题的思路无独有偶，可以用深度搜索遍历。
只是其中的tt数组有两个功能，一个是表示是否这个为陷阱，还有一个功能是要他来表示边界，因为tt数组定义在栈中，即为全局变量，所以默认都是0，所以又要表示出边界，只能初始化为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
int tt[6][6];//这是存储地图中障碍点的信息
bool temp[6][6];//temp是标记此点是否走过
int n,m,t;
int total;
int tx,ty;
int sx,sy,fx,fy;

void dfs(int x,int y){
    if(x==fx&&y==fy){//如果能达到终点
        total++;//总数加1
        return;
    }
    else{
        for(int i=0;i<=3;i++){
            if(temp[x+dx[i]][y+dy[i]]==0&&tt[x+dx[i]][y+dy[i]]==1){
                //如果没有走过这个点，且他不是障碍点的话，
                temp[x][y]=1;//就选择走这个点，即先将这个点标记为走过
                dfs(x+dx[i],y+dy[i]);//然后递归
                temp[x][y]=0;//递归出口，要将这个点的标记复原
            }
        }
    }
}

int main(){
    cin>>n>>m>>t;//输入长度宽度，障碍个数
    cin>>sx>>sy>>fx>>fy;//输入起始地点和结束地点
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            tt[i][j]=1;//先默认标记地图中的点为1
        }
    }
    
    for(int k=1;k<=t;k++){
        cin>>tx>>ty;
        tt[tx][ty]=0;//输入障碍点,如果是障碍点就将此处的标记设为0
    }

    dfs(sx,sy);
    cout<<total<<endl;
    return 0;
}

填涂颜色
题目链接
DFS题解如下：
注意下题再输入的时候是从i=1，j=1处输入的，但是数组的行，列都是从0，0开始的，所以，我们输入的数组，没有贴着数组输入，输入的数字是被外面一圈0包围着的。这样，就不会如果输入的数据一开始就是包围圈，递归就停止递归了。就不会出现上述这种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

int a[32][32],b[32][32];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int n,j,i;

void dfs(int x,int y){
    int i;
    if(x<0||x>n+1||y<0||y>n+1||a[x][y]!=0)  return;//如果越界或者碰到闭合圈，退出
    a[x][y]=1;//染色
    for(i=1;i<=4;i++){
        dfs(x+dx[i],y+dy[i]);//对当前位置的上下左右四个方位递归
    }
}

int main(){
    cin>>n;
    for(i=1;i<=n;i++){//注意是从1开始输入
        for(j=1;j<=n;j++){
            cin>>b[i][j];
            if(b[i][j]==0)  a[i][j]=0;
            else    a[i][j]=2;
        }
    }

    dfs(0,0);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(a[i][j]==0)  cout<<2<<' ';//如果此时还是0，说明这些0是闭合圈里的
            else    cout<<b[i][j]<<' ';//输出闭合圈
            
        }
        cout<<'\n';
    }
    return 0;
}

字串变化
题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;

const int maxn=15;

string aa;//
string b;
int n,ans;

struct node{
    string a;
    int step;
};
string shi[maxn];
string zhong[maxn];

map<string,int> ma;//建立string型与int型的映射,用来判重

string pin(const string &a,int i,int j){//拼接函数
    //对于要拼接的串a，我们试图在他的第i个位置用第j种手段去改变
    //然后去判断此改变是否合法，如果合法就压入队列，再次搜索
    string ans="";
    if(i+shi[j].length()>a.length()){
        return ans;
    }
    for(int k=0;k<shi[j].length();k++){
        if(a[i+k]!=shi[j][k]) return ans;
    }
    ans=a.substr(0,i);
    ans+=zhong[j];
    ans+=a.substr(i+shi[j].length());
    return ans;
}

void bfs(){
    queue<node> q;
    node s;
    s.a=aa;//先将输入的字符串，
    s.step=0;
    q.push(s);//入队

    while(!q.empty()){
        node u=q.front();//将队首结点赋给u
        q.pop();//出队
        string temp;
        if(ma.count(u.a)==1){//count函数是map中判断关键字是否出现
            //优化一下，如果重复的路径就continue
            continue;
        }
        if(u.a==b){//如果等于最后需要的字符串
            ans=u.step;
            break;
        }
        ma[u.a]=1;//标记为1
        //下面的双重for循环的含义是：
        //枚举当前队列中队头那个串的每一个字符，且对每一个字符
        //枚举所有的可能转换的情况，然后去尝试拼接
        for(int i=0;i<u.a.length();i++){
            for(int j=0;j<n;j++){
                temp=pin(u.a,i,j);
                if(temp!=""){
                    node v;
                    v.a=temp;
                    v.step=u.step+1;
                    q.push(v);
                }
            }
        }
    }
    if(ans>10||ans==0){
        cout<<"NO ANSWER!"<<endl;
    }
    else{
        cout<<ans<<endl;
    }
    
}
int main(){
    cin>>aa>>b;//输入两个字符串
    while(cin>>shi[n]>>zhong[n])    n++;//因为不知道输入多少个转换条件，所以就用while判定
    bfs();//调用bfs
    return 0;   
}