BFS小结（持续更新中）

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;
}

分享到：