`
java-mans
  • 浏览: 11342646 次
文章分类
社区版块
存档分类
最新评论

BFS小结(持续更新中)

 
阅读更多

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove


刚好yobobobo最近做BFS,我也被渲染了,当是复习一下,也总结一下吧,大部分是HDOJ上的BFS题目,由于本人时间有限,会持续更新


HDU 1548 http://acm.hdu.edu.cn/showproblem.php?pid=1548

基础的BFS,每次有两个方向,分别把步数乘以1和-1就行了。其余的都是基础BFS,注意下起点终点重合的情况


HDU 1372http://acm.hdu.edu.cn/showproblem.php?pid=1372

经典的马步移动,基本的BFS改成8个方向,同样处理即可


HDU 2717 http://acm.hdu.edu.cn/showproblem.php?pid=2717

3种情况移动,+1,-1,*2,没啥好说的,同样处理就行了,同时注意下边界,比目标大的话就只能全部-1,如果比目标大了就没必要*2


HDU 3766 http://acm.hdu.edu.cn/showproblem.php?pid=3766

比较坑,开始以为和1372一样,其实不是,这题没有给出范围,但是范围很大,之前需要逼近下,然后再搜索,或者直接枚举判断下就行了


HDU 1026 http://acm.hdu.edu.cn/showproblem.php?pid=1026

其实做法一样,需要打怪耗时,需要用优先队列或者最小堆来处理下,不过这题比较纠结的是需要输出路径,首先注意细节问题,之前用的是next,保存后继结点,果断被坑,一个点在搜索的时候的后继结点会有好多,果断改成pre,前趋表示。


HDU 1072 http://acm.hdu.edu.cn/showproblem.php?pid=1072

题目总体思路很明确,遇到数字4的话,时间重置下,在判重的时候需要用三维数组,加一个当前时间,如果两次到某点剩余时间相同,那就没必要再走了。


HDU 1175 http://acm.hdu.edu.cn/showproblem.php?pid=1175

弱爆了,果断也被坑了,开始觉得只要保存某个结点的方向和已拐的弯,然后搜索就行了,其实只要沿某条直线先一直搜到底就行了,不过还是要保存方向和已拐的弯的个数。


HDU 1180 http://acm.hdu.edu.cn/showproblem.php?pid=1180

注意下楼梯部分的细节问题就行了,可以停在原地等待楼梯转向,这里比较坑啊,而且楼梯处不需要标记,可能两个方向都要走


HDU 1242 http://acm.hdu.edu.cn/showproblem.php?pid=1242

果断BFS+优先队列


HDU 1728 http://acm.hdu.edu.cn/showproblem.php?pid=1728

类似于连连看,限制了拐弯次数,只需要每个方向走到底就行了,题目输入有些坑,行列有点混乱应注意。而且如果之前搜过的点,之后不能停止而是跳过。


HDU 2579 http://acm.hdu.edu.cn/showproblem.php?pid=2579

由于 在K的倍数的时候石头会消失,所以不能像其它迷宫问题一样判重,可能当前时间石头还在,而走一圈再回来石头消失,也许就有其它的路径可以走,因此判断的时候要加上三维数组flag[x][y][time%k],如果到某点的时间取余都相同,那么此时的状态就是完全相同,没有意义的

HDU 2012 http://acm.hdu.edu.cn/showproblem.php?pid=2102
三维的BFS,注意一些细节就行了,譬如进入传送门就必须传送,而且另一边必须只有是空地才行,坑死了,读题不仔细

HDU 1253 http://acm.hdu.edu.cn/showproblem.php?pid=1253

三维BFS,木有问题,注意优化下

HDU 1240 http://acm.hdu.edu.cn/showproblem.php?pid=1240

三维BFS水之


HDU 1429 http://acm.hdu.edu.cn/showproblem.php?pid=1429

BFS+二进制压缩存储,很明显要保存你拿过的钥匙的状态,总共10把钥匙,使用二进制压缩才1024个状态,开始还打算把门的状态也保存下来,结果莫名其秒的TLE,后来发现只需要钥匙的状态,因为钥匙可以用很多次,但是又莫名其妙的MLE,好吧,不解释,彻底晕了flag[x][y][key],表示在(x,y)手上钥匙状态为key


HDU 1254 http://acm.hdu.edu.cn/showproblem.php?pid=1254

经典的推箱子游戏,注意判重需要一个三维数组,可用两次B FS解决,或者BFS+DFS

详情请移步 http://blog.csdn.net/acm_cxlove/article/details/7639306


HDU 2612 http://acm.hdu.edu.cn/showproblem.php?pid=2612

两个人到同一点的和最短,分别以两个人为起点,遍历整个图,计算出到每个KFC的最短距离,然后枚举所有的KFC,算最小的代价


HDU 1983 http://acm.hdu.edu.cn/showproblem.php?pid=1983

最差的情况直接把出口或者入口四个方向封住,所以最多只要堵4次。BFS找出最短的路径,并保存路径,DFS处理路径上的点,BFS判断是否连通。


HDU 1195 http://acm.hdu.edu.cn/showproblem.php?pid=1195

题目不难,1W个可能,判重很简单,就是转化有点纠结,至少我写得很矬


HDU 2128 http://acm.hdu.edu.cn/showproblem.php?pid=2128

坑爹的题目,不过题目很好,BFS和DFS都可以做

具体请见http://blog.csdn.net/acm_cxlove/article/details/7635497


贴代码:

HDU 1240 三维BFS

/*
ID:cxlove
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL unsigned long long
using namespace std;
int n,m,q;
int way[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
char str[15][15][15];
bool flag[15][15][15];
struct Node{
	int x,y,z,step;
	bool check(){
		if(x>=0&&y>=0&&z>=0&&x<n&&y<n&&z<n)
			return true;
		return false;
	}
}s,e,u,v;
int bfs(){
	if(s.x==e.x&&s.y==e.y&&s.z==e.z)
		return 0;
	queue<Node>que;
	memset(flag,false,sizeof(flag));
	s.step=0;
	que.push(s);
	flag[s.x][s.y][s.z]=true;
	while(!que.empty()){
		u=que.front();
		que.pop();
		for(int i=0;i<6;i++){
			v=u;
			v.x+=way[i][0];
			v.y+=way[i][1];
			v.z+=way[i][2];
			v.step++;
			if(v.check()&&flag[v.x][v.y][v.z]==false){             
				flag[v.x][v.y][v.z]=true;
				if(v.x==e.x&&v.y==e.y&&v.z==e.z)
					return v.step;
                if(str[v.x][v.y][v.z]=='X')
                    continue;
				que.push(v);
			}
		}
	}
	return -1;
}
char ch[100];
int main(){
	while(scanf("%s%d",ch,&n)!=EOF){
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
					scanf("%s",str[i][j]);
		while(scanf("%s",ch)){
			if(strcmp(ch,"END")==0)
				break;
			sscanf(ch,"%d",&s.x);
			scanf("%d%d%d%d%d",&s.y,&s.z,&e.x,&e.y,&e.z);
			int ans=bfs();
			if(ans==-1)
				printf("NO ROUTE\n");
			else
				printf("%d %d\n",n,ans);
		}

	}
	return 0;
}

HDU 1728 限制拐弯次数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL unsigned long long
using namespace std;
int n,m,k;
int way[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char str[105][105];
bool flag[105][105];
struct Node{
    int x,y,dir,cnt;
    bool check(){
        if(x>=0&&x<n&&y>=0&&y<m)
            return true;
        return false;
    }
}s,e,u,v;
int bfs(){
    queue<Node>que;
    que.push(s);
    memset(flag,false,sizeof(flag));
    flag[s.x][s.y]=true;
    while(!que.empty()){
        u=que.front();
        que.pop();
        for(int i=0;i<4;i++){
            v.cnt=u.cnt;
            if(u.dir!=-1&&u.dir!=i)
                v.cnt++;
            if(v.cnt>k)
                continue;    
            v.dir=i;
            for(int j=1;;j++){
                v.x=u.x+way[i][0]*j;
                v.y=u.y+way[i][1]*j;
                if(v.check()&&str[v.x][v.y]!='*'){
                    if(flag[v.x][v.y])
                        continue;
                    flag[v.x][v.y]=true;
                    if(v.x==e.x&&v.y==e.y)
                        return true;
                    que.push(v);
                }
                else
                    break;
            }
        }
    }
    return false;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%s",str[i]);
        scanf("%d%d%d%d%d",&k,&s.y,&s.x,&e.y,&e.x);
        s.x--;s.y--;e.x--;e.y--;
        s.cnt=0;s.dir=-1;
        if((s.x==e.x&&s.y==e.y)||bfs())
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

HDU 1242 BFS+优先队列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
struct Node{
    int x,y,step;
    bool operator<(const Node &n1)const{
        return step>n1.step;
    }
}s,e,u,v;
int n,m;
char str[205][205];
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int bfs(){
    priority_queue<Node>que;
    bool flag[205][205];
    memset(flag,0,sizeof(flag));
    s.step=0;
    que.push(s);
    flag[s.x][s.y]=1;
    while(!que.empty()){
        u=que.top();
        que.pop();
        for(int i=0;i<4;i++){
            v.x=u.x+way[i][0];
            v.y=u.y+way[i][1];
            if(v.x>=0&&v.y>=0&&v.x<n&&v.y<m&&flag[v.x][v.y]==0&&str[v.x][v.y]!='#'){
                flag[v.x][v.y]=1;
                if(str[v.x][v.y]=='x')
                    v.step=u.step+2;
                else
                    v.step=u.step+1;
                if(v.x==e.x&&v.y==e.y)
                    return v.step;
                que.push(v);
            }
        }
    }
    return -1;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%s",str[i]);
            for(int j=0;j<m;j++)
                if(str[i][j]=='a'){
                    s.x=i;
                    s.y=j;
                }
                else if(str[i][j]=='r'){
                    e.x=i;
                    e.y=j;
                }
        }
        int ans=bfs();
        if(ans==-1)
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

    


HDU 1429 BFS+二进制压缩

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define LL unsigned long long
using namespace std;
int n,m,T;
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char str[21][21];
bool flag[21][21][1024];
struct Node{
	short x,y,step;
	short key;
	bool check(){
		if(x>=0&&x<n&&y>=0&&y<m)
			return true;
		return false;
	}
}s,e,u,v;
queue<Node>que;
int bfs(){
	if(!que.empty())
	    que.pop();
	que.push(s);
	memset(flag,false,sizeof(flag));
	while(!que.empty()){
		u=que.front();
		que.pop();
       
		for(int i=0;i<4;i++){
			v=u;
			v.step++;
			v.x+=way[i][0];
			v.y+=way[i][1]; 
            
	      	if(v.step>=T)
		        break;
			if(v.check()&&str[v.x][v.y]!='*'){
              	if(str[v.x][v.y]=='^')
		    	    return v.step;
				if(str[v.x][v.y]>='A'&&str[v.x][v.y]<='J'){
					if(((1<<(str[v.x][v.y]-'A'))&v.key)&&flag[v.x][v.y][v.key]==false){
						que.push(v);
						flag[v.x][v.y][v.key]=true;
					}
				}
				else if(str[v.x][v.y]>='a'&&str[v.x][v.y]<='j'){
                    v.key|=(1<<(str[v.x][v.y]-'a'));
                    if(flag[v.x][v.y][v.key]==false){			
				    	que.push(v);
				    	flag[v.x][v.y][v.key]=true;
                    }
				}
				else{  //相当于空地
					if(!flag[v.x][v.y][v.key]){
						flag[v.x][v.y][v.key]=true;
						que.push(v);
					}
				}
			}

		}
	}
	return -1;
}
int main(){
	while(scanf("%d%d%d",&n,&m,&T)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%s",str[i]);
			for(int j=0;j<m;j++){
				if(str[i][j]=='@'){
					s.x=i;
					s.y=j;
					s.step=0;
					s.key=0;
				}
			}
		}
		printf("%d\n",bfs());
	}
	return 0;
}







分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics