投稿
  1. 首页
  2. 随笔

BFS+DFS

电子技术应用专业 • 2022-12-16 • 随笔 • 阅读 79

BFS+DFS,第1张

BFS+DFS

DFS+BFS刷题日记
  • Catch That Cow
  • 6264:走出迷宫（BFS、DFS剪枝）
  • 1159:Maze(BFS不止一次，没有限制的BFS一次可以遍历所有节点，一旦对某些节点加以限制，那么限制的节点可以到达却不入队，它的拓展节点自然不能通过它被访问到更别提入队，一次BFS之后再判断限制的节点能否入队，入队之后，以该限制节点为起始节点BFS

Catch That Cow

题意：
John在坐标n上，可以左移右移加跳跃，牛在坐标k上且不动，至少多久抓住牛

//#include
#include
#include 
using namespace std;
#include 
#include 
const int MAXX=100000;
struct node{
	int x;
	int step;//这个点的位置是x，从出发点走了step步，一步一分钟
	node(int xx,int s):x(xx),step(s){} //这种构造方法 
	node(){}//空的构造函数，才允许node p 
};
//queue a[MAXX+10];和vector不同 
queue a;
int vis[MAXX+10];//给下标 设置判重标记，看看这个节点是否已经被扩展过 
int main(){
	ios_base::sync_with_stdio(0);
	int n,k;//John在坐标n上，可以左移右移加跳跃，牛在坐标k上且不动，至少多久抓住牛
	cin>>n>>k;
	memset(vis,0,sizeof(vis)); 
	node p;
	p.x=n;
	p.step=0;
	a.push(p);//第一步先把初始节点放入队列 
	vis[n]=1;
	while(!a.empty()){//队列不为空就逐一出队，并将出队的节点的邻接节点入队 
		node q=a.front();
		if(q.x==k){
			cout<=0&&!vis[q.x-1]) {
//				q.x=q.x-1;怎么重新创建一个匿名的node对象 
//				q.step=q.step+1;
				a.push(node(q.x-1,q.step+1)) ;
				vis[q.x-1]=1;
			}
				if(q.x+1<=MAXX&&!vis[q.x+1]) {
				a.push(node(q.x+1,q.step+1)) ;
				vis[q.x+1]=1;
			}
			if(2*q.x<=MAXX&&!vis[2*q.x]) {
				a.push(node(2*q.x,q.step+1)) ;
				vis[2*q.x]=1;
			}
			a.pop();
		}
	} 
    return 0;
}
6264:走出迷宫（BFS、DFS剪枝）

传送门
题意：假设你已经得到了一个n*m的迷宫的图纸，已知起点和终点坐标，请你找出从起点到出口的最短路。
BFS板子题

//#include
#include
#include 
using namespace std;
#include 
#include 
int m,n;
int ex,ey;
struct node{
	int x;
	int y;
	int step;
	node(int xx,int yy,int steps):x(xx),y(yy),step(steps){};
};
char a[105][105];
int vis[105][105];
int dx[4]={-1,1,0,0};//上下左右 
int dy[4]={0,0,-1,1};
int main(){
	ios_base::sync_with_stdio(0);
	queue q;
	cin>>m>>n;
	for(int i=0;i>a[i];
	}
	memset(vis,0,sizeof(vis));
	for(int i=0;i=0&&cx=0&&cy 

 
 
int lastminL[105][105];
 时间换空间，剪枝来了，dfs要逐一走很多条路
 且每条路都走到终点罢休所以超时，而且每次都只单独存储正在走的这一条路
 不知道别的路情况怎么样，比如走到同一个点a[i][j],上一条路用了x步，
 这条路用了y步，那这条路自然就不继续走下去了，return。但由于只
 单独存储一条路，无法与别的路进行比较，因此空间换时间，用这个数组lastminL[i][j]
 记录之前走的若干条路走到a[i][j]时用的最小步数，如果再走一条路走到这个点，用的
 步数超过了 lastminL[i][j]，那么这条路就不用走了
 就像寻路问题ROADS那题(找最短路径)，也开了一个数组minL[i][j]表示从1走到城市i
 且经费还剩j时所走的长度，如果后续的路上恰好走到i剩j钱且走的路长于minL[i][j]就不走了
 还有一个剪枝条件，（最优性剪枝和可行性剪枝，暂时对不上号）
 就是也许有的路已经走完得到结果需要走minx这么长，可这条路某阶段已经超过minx就pass
 

 

 
 
对了还有一个值得注意的地方就是设置无穷大的值的时候，一会儿１＜＜３０，一会儿０ｘ３ｆ３ｆ３ｆ
 这样就会出问题噢
 step　既与　lastminL[x][y]（初始化为１＜＜３０）比较
 又与ｍｉｎｘ（初始化为　０ｘ３ｆ３ｆ３ｆ）比较
 虽然我还没扪清到底哪一步　让ｍｉｎｘ与lastminL[x][y]间接比上了
 

 

#include 		
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int m,n; 
char a[105][105];
	int ps,qs,pe,qe;
int minx=1<<30;//也可以用1<<30;这种形式表示一个很大的数 
int dx[4]={-1,1,0,0};//上下左右 
int dy[4]={0,0,-1,1};
int vis[105][105];
//int step=-1; 
int lastminL[105][105];//到上次路为止走到a[i][j]用的最少步数（比出来的） 
void dfs(int x,int y,int step){//第x行，第y列 
	 if(vis[x][y])return;
	 if(step>=minx)return;
		 if(step>=lastminL[x][y])return;
		 else lastminL[x][y]=step;//lastminL[i][j]是逐一比较更新出来的 
	 		vis[x][y]=1;
	 		if(x==pe&&y==qe){
	 			minx=min(minx,step);
//dfs是每一条路径都走遍了才确定找出最小的step 
	 			return;
			 }
	 	for(int i=0;i<4;i++){
//	 		step=kkk;//dfs没有搜到是要回溯的。。。回到原来的step,每次step--也行 
	 		int cx=x+dx[i];
	 		int cy=y+dy[i];
	 		if(cx>=0&&cx=0&&cy>m>>n;
	for(int i=0;i>a[i];
	}
	for(int i=0;i 

保留注释部分是为了更好地与没剪枝的样子对比
 下面是没剪枝的ｔｌｅ代码
 

#include 		
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int m,n; 
char a[105][105];
	int ps,qs,pe,qe;
int minx=0x3f3f3f3f;//也可以用2<<30;这种形式表示一个很大的数 
int dx[4]={-1,1,0,0};//上下左右 
int dy[4]={0,0,-1,1};
int vis[105][105];
int step=-1; 
void dfs(int x,int y){//第x行，第y列 
	 if(vis[x][y])return;
	 else{
	 		vis[x][y]=1;
	 		step++;
	 		if(x==pe&&y==qe){
	 			minx=min(minx,step);
//dfs是每一条路径都走遍了才确定找出最小的step 
	 			return;
			 }
		int kkk=step;
	 	for(int i=0;i<4;i++){
	 		step=kkk;//dfs没有搜到是要回溯的。。。回到原来的step 
	 		int cx=x+dx[i];
	 		int cy=y+dy[i];
	 		if(cx>=0&&cx=0&&cy>m>>n;
	for(int i=0;i>a[i];
	}

	for(int i=0;i 
1159:Maze(BFS不止一次，没有限制的BFS一次可以遍历所有节点，一旦对某些节点加以限制，那么限制的节点可以到达却不入队，它的拓展节点自然不能通过它被访问到更别提入队，一次BFS之后再判断限制的节点能否入队，入队之后，以该限制节点为起始节点BFS 

题意：A—E五道门，迷宫中有几把对应的钥匙a—e(A对应a）就需要集齐所有的钥匙才能开对应的这道门，问从起始点能否到达终点（终点可能被门或墙围拦住，导致BFS永远遍历不到
 

#include
#include 
#include 
using namespace std;
const int maxn=40;
struct Node{
    int x,y;
    Node() {}
    Node(int xx,int yy){
        this->x=xx;
        this->y=yy;
    }
 
};
//钥匙/门的哈希值相同 通过门的哈希值找到对应的钥匙  A a
struct Door{
    int num;   //总共数量
    int sum;  //遇到的数量
}door[maxn];
 
queue Q;
char G[maxn][maxn];
int n,m;
int vis[maxn][maxn],vis_door[maxn];
const int go[][2]={1,0,
                   -1,0,
                   0,1,
                   0,-1};
void init(){
    while(!Q.empty()) Q.pop();
    memset(vis,0,sizeof(vis));
    memset(vis_door,0, sizeof(vis_door));
    for(int i=0;i>G[i][j];
            if(G[i][j]>='a' && G[i][j]<='e'){
                door[G[i][j]-'a'].num++;   //hash
            }
            else if(G[i][j]=='S'){
                vis[i][j]=1;
                Q.push(Node(i,j));
            }
        }
 
    }
 
}
 
bool inside(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m ;
}
void BFS(){
    bool f=true;
    while(f){
        //bfs + 标记门和钥匙
        while(!Q.empty()){
            //如果出口
            Node cur=Q.front(); Q.pop();
            int x=cur.x,y=cur.y;
            if(G[x][y]=='G'){
                cout<<"YES"<='a' && c<='e'){
                        door[c-'a'].sum++;
                    }
                    else if(c>='A' && c<='E'){
                        vis_door[c-'A']=1;
                        continue; //注意这个位置  队列里加入的到底是啥
                    }
                    vis[xx][yy]=1;
                    Q.push(Node(xx,yy));//除了墙和门不能入队，哪怕是终点也可以直接入队，如果在碰见门之前碰见了终点，直接入队，BFS说明 终点比门离起点更近 
                }
            }//出队并对出对元素进行拓展（看情况让拓展的元素入队） 
 
        }//完成了一轮BFS，队列已经为空了，终点没进过队，要么是被墙挡住了要么是被门挡住了 
        f=false;
        //检查门能不能开 vis_door
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(G[i][j]>='A' && G[i][j]<='E' && !vis[i][j] ){
                    char c=G[i][j];
                    int id=c-'A';
                    if(vis_door[id] && door[id].num>0 && door[id].num==door[id].sum){
                        vis[i][j]=1;
                        Q.push(Node(i,j));//是被门挡住了且钥匙已经集齐，将门入队，那么再一轮BFS(从队列队首元素开始，如果终点是被门挡住的，终点就会作为该门的拓展节点入队 
                        f= true;
                    }
                }
            }
 
        }
 
    }
    cout<<"NO"<>n>>m && (n&&m)){
        init();
        read();
        BFS();
    }
    return 0;
}

 

自己再来一遍
 

 #include
using namespace std;
int m,n;
char a[25][25];
int dx[4]={1,-1,-0,0};
int dy[4]={0,0,1,-1};
struct node{
	int x;
	int y;
	node(int xx,int yy):x(xx),y(yy){};
};
struct door{
	int num;//对于这扇门共有多少把钥匙 
	int sum; //对于这扇门集齐了多少把钥匙 
}door[5];
queue q;
int vis_door[5];//终点不能入队，记录是不是门挡住的 
int vis[25][25];
void bfs(){
	int flag=true;
	while(flag){
			while(!q.empty()){//开始来一次bfs全扫一遍 
		node p=q.front(); q.pop();//放在循环体中的最后一条也行 
		 if(a[p.x][p.y]=='G'){
		 	cout<<"YES"<=0&&cx=0&&cy='a'&&a[cx][cy]<='e'){
							door[a[cx][cy]-'a'].sum++;
							//记录找到的钥匙，这个节点是要入队的，不能用 continue； 
						} 
						else if(a[cx][cy]>='A'&&a[cx][cy]<='E') {
							vis_door[a[cx][cy]-'A']=1;
							continue;//门是不能直接入队的 
						}
						vis[cx][cy]=1;
						q.push(node(cx,cy));
					}
			 }
		 } 
	}//一次bfs结束了，如果到达了终点会return，否则还要看看终点没入队是不是被门
//挡住了，如果门能开那还有到达终点的希望，将门入队（即以门为起始节点再进行BFS扩展 
 	flag=false;
	 for(int i=0;i='A'&&a[i][j]<='E'&&!vis[i][j]){
	 			if(vis_door[a[i][j]-'A']&&door[a[i][j]-'A'].num==door[a[i][j]-'A'].sum){
	 				flag=true;
	 				vis[i][j]=1;
	 				q.push(node(i,j));
				 }
			 }
		 } 
	 } //如果没有一扇门能打开看看能否拓展到终点,就be了 
//	  if(!flag)cout<<"NO"<>m>>n){
		if(m==0&&n==0)return 0;
		
		while(!q.empty())q.pop();
		memset(vis,0,sizeof(vis));
		memset(vis_door,0,sizeof(vis_door));
		for(int i=0;i<5;i++){
			door[i].num=0;
			door[i].sum=0;
		}//因为有多组数据，一定要完完整整地全盘初始化 
		for(int i=0;i>a[i][j];
				if(a[i][j]=='S'){
//					sx=i; sy=j;
				q.push(node(i,j));//将起始节点入队了 
				vis[i][j]=1; 
				}
				if(a[i][j]>='a'&&a[i][j]<='e'){//累计有多少把钥匙 
					door[a[i][j]-'a'].num++; 
				}
			}
		} 
		bfs(); 
	}
    return 0;
} 

 

TLE，问题在于vis数组的置1 和 push入队 是否被忘记
 第一次BFS，但凡不是墙，不是门，且！vis[i][j]没被拓展进队过，就应该push进队且勿忘vis【i】【j】置1
 第一次BFS没能到达目标点，之后要看目标点没能入队的原因是被墙拦住了（没救了）还是被门拦住了（有希望，如果到达过该门且现在该门对应的钥匙集齐了，就应该将该门入队展开BFS，同时由于该门入队了，vis【i】【j】要置为1，判断是否入队时忘记了**！vis【i】【j】**这个条件
 第一次BFS到达了门却不管钥匙情况，一概不让门入队，应为要等BFS走完所有能走的地方收集完所有能收集的钥匙之后才能确保一扇门是否能被打开。
 由于没有保留所有门的坐标，还需要从a迷宫数组中去找门，会找到所有的门并把全部能开的门都入队，届时就可以通过这些点为中心BFS，万一通过　第一次找到能入队的门　还是不能到达终点，但是可能集齐了另外的钥匙能进入上次开不了的门，所以要再遍历ａ迷宫数组去找能开的门，这时就要避免被上次开过的门蒙蔽了，上回开过且没找到，又通过这扇门去BFS，时间就耗在这儿了，所以开过的门（入过队的门也要标记ｖｉｓ【ｉ】【ｊ】为１，下次得有别的新的门能够打开才有希望寻到新的地方（也许存在目标点）
 逻辑有点多，遵循规则就好，凡是入队过（BFS拓展过的节点，ｖｉｓ【ｉ】【ｊ】统统置为１，找能否入队的点也一定要判断　！ｖｉｓ【ｉ】【ｊ】，避免重复入队，这个节点能BFS到的范围已经考虑过了，再寻无意义，不会有新发现。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5657841.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
电子技术应用专业 电子技术应用专业 一级用户组
0 0
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表（0条）

保存