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