bfs原理
 
bfs就是广度优先搜索，与深度优先搜索有类似之处也有不同之处。
 深度优先搜索是不撞南墙不回头的莽夫。
 
 而广度优先搜索则像高塔一样稳健。
 
 所以说广度优先搜索总是能找到一个问题的最优解，但它没有深搜那么莽夫，所以广搜所要花费的时间往往比深搜要久。
 
bfs的建立
 
bfs要先建立一个队列
 
struct node
{
	int ;//至少两个，一个表示数据，一个表示数据所在的位置。
};
 
用这个结构体来表示每一步与每一步所在的位置。
 
区别
 
dfs考虑的是当先该怎么做并用递归写出下一次，而bfs考虑的是下一次有几种做法。
 我这里给出dfs的文章做对比dfs原理
 
例题
 
为了直观的显现出bfs与dfs的区别，我们用bfs来解我之前在dfs上的原题：
 
B先生在一个迷宫里迷路了，他需要A先生的救助，A先生也不知道怎么走，所以他只能一步一步试。
 现在编程来帮A先生解救B先生。
 
输入
 
m，n代表迷宫的长与宽。
 m行，n列0或1.其中0代表路，1代表障碍。
 出发坐标（x，y）与目标坐标（sx，sy）
 
输出
 
最短步数。
 
输入样例
 
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
 
输出样例
 
7
 
我们先建立一个结构体
 
#include<stdio.h>
struct node
{
	int x,y,s;//x，y为坐标，s为步数。
};
 
接下来是地图初始化与输入
 
truct node que[2501];//地图
 	int a[51][51]={0},book[51][51]={0};
 	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向
 	int head,tail;
 	int i,j,k,m,n,sx,sy,p,q,tx,ty,flag;
 	scanf("%d%d",&n,&m);//初始化地图
 	for(i=1;i<=n;++i)
 		for(j=1;j<=m;++j)
 			scanf("%d",&a[i][j]);
 	scanf("%d%d%d%d",&sx,&sy,&p,&q);//队列初始化
 	head=1;    //其他值的初始化
 	tail=1;
 	que[tail].x=sx;
 	que[tail].y=sy;
 	que[tail].s=0;
 	tail++;
 	book[sx][sy]=1;
 	flag=0;
 
接下来是bfs的关键
 
如果用dfs，我们就用一个dfs函数来模拟每一步。
 
void dfs(int x,int y,int step)
{
	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	int i,nx,ny;
	if(x==p&&y==q){
		if(step<min)
			min=step;
		return;
	}	
	for(i=0;i<=3;++i){
		nx=x+next[i][0];
		ny=y+next[i][1];
		if(nx<1||ny<1||nx>n||ny>m)
			continue;
		if(a[nx][ny]==0&&book[nx][ny]==0){
			book[nx][ny]=1;
			dfs(nx,ny,step+1);
			book[nx][ny]=0;
		}	
	}
	return;
}
 
如果用bfs则：
 
1. 首先判断这个地方走没走过 *head<tail*
 2. 列举四分方向
 
for(k=0;k<=3;++k){
 			tx=que[head].x+next[k][0];
 			ty=que[head].y+next[k][1];
 			if(tx<1||tx>n||ty<1||ty>m)
 				continue;
 			if(a[tx][ty]==0&&book[tx][ty]==0){//这里判断这一步是否走过
 				book[tx][ty]=1;
 				que[tail].x=tx;
 				que[tail].y=ty;
 				que[tail].s=que[head].s+1;
 				tail++;
			}
 
3.如果找到目的地了flag=1;并break;
 
if(tx==p&&ty==q){
	flag=1;
	break;
}
 
4.如果flag=1;则代表这里条路已经走完了，则进行下一次尝试head++
 
bfs部分完整代码：
 
while(head<tail){
 		for(k=0;k<=3;++k){
 			tx=que[head].x+next[k][0];
 			ty=que[head].y+next[k][1];
 			if(tx<1||tx>n||ty<1||ty>m)
 				continue;
 			if(a[tx][ty]==0&&book[tx][ty]==0){//和dfs一样乱七八糟的判断
 				book[tx][ty]=1;
 				que[tail].x=tx;
 				que[tail].y=ty;
 				que[tail].s=que[head].s+1;
 				tail++;
			}
			 if(tx==p&&ty==q){
			 	flag=1;
			 	break;
			}
		}
		if(flag==1)
			break;
		head++;
	}
 
在进行完这些步骤之后。最少的步数就模拟出来了。
 接下来只需要进行一个简单的printf即可。
 
完整代码
 
#include<stdio.h>
struct node
{
	int x,y,s;//x，y为坐标，s为步数。
};
 
 int main()
{
	struct node que[2501];//地图
 	int a[51][51]={0},book[51][51]={0};
 	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向
 	int head,tail;
 	int i,j,k,m,n,sx,sy,p,q,tx,ty,flag;
 	scanf("%d%d",&n,&m);//初始化地图
 	for(i=1;i<=n;++i)
 		for(j=1;j<=m;++j)
 			scanf("%d",&a[i][j]);
 	scanf("%d%d%d%d",&sx,&sy,&p,&q);//队列初始化
 	head=1;
 	tail=1;
 	que[tail].x=sx;
 	que[tail].y=sy;
 	que[tail].s=0;
 	tail++;
 	book[sx][sy]=1;
 	flag=0;
 	while(head<tail){
 		for(k=0;k<=3;++k){
 			tx=que[head].x+next[k][0];
 			ty=que[head].y+next[k][1];
 			if(tx<1||tx>n||ty<1||ty>m)
 				continue;
 			if(a[tx][ty]==0&&book[tx][ty]==0){//和dfs一样乱七八糟的判断
 				book[tx][ty]=1;
 				que[tail].x=tx;
 				que[tail].y=ty;
 				que[tail].s=que[head].s+1;
 				tail++;
			}
			 if(tx==p&&ty==q){
			 	flag=1;
			 	break;
			}
		}
		if(flag==1)
			break;
		head++;
	}
	printf("%d",que[tail-1].s);
	return 0;
}

BFS -> 僵尸感染 -> 队列
 
每个点状态的数量 ，每个状态访问一次，想办法将状态转换为int（类似hash）
 
int visted = [x][y][状态数量]; 
 Queue queue;
 
void bfs(起点){ 
 if起点符合退出条件，return
 
  起点入队
  while(队列不为空){
      当前临时点 = queue出队
      for（各个方向遍历）{
          根据当前临时点得到下一个点的位置
         if(下一个点的visted没有访问过&&其他条件成立)
             下一个点入队
             更新下一个的信息(比如到达step)
             如果符合退出条件，return
             else 继续
         }
      } 
 }
 
}
 
POJ 1324
 
#include <cstdio>
#include <iostream>

using namespace std;
#define SIZE 20
#define LENGTH 8
#define SNAKE_STATES 16384 //状态数量，以蛇头为起点，向后的每个点都有4中状态（取整），就提取了特征值

int snake[LENGTH][2];
int stone[SIZE * SIZE][2];

int visited[SIZE + 1][SIZE + 1][SNAKE_STATES];
typedef struct Element{
    int x;
    int y;
    int state;
    int step;
} Element;

Element Queue[SIZE * SIZE * SNAKE_STATES];
int head, tail;


int direct[3][3] = {
    0, 0, 0,
    3, 0, 1,
    0, 2, 0,
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int getState(int Len){
    int state = 0;
    for(int i = Len - 1; i > 0; i--){
        int x = snake[i][0] - snake[i - 1][0];
        int y = snake[i][1] - snake[i - 1][1];
        x+=1;
        y+=1;
        int D = direct[x][y];
        state = state * 4 + D;
    }
    return state;
}

int isStone(int x, int y, int K){
    for(int i = 0; i < K; i++){
        if(x == stone[i][0] && y == stone[i][1])
            return 1;
    }
    return 0;
}

int isSnake(int x, int y, int state, int L, int nx, int ny){
    snake[0][0] = x;
    snake[0][1] = y;
    for(int i = 1; i < L; i++){
        int D = state % 4;
        state = state / 4;
        snake[i][0] = snake[i - 1][0] + dx[D];
        snake[i][1] = snake[i - 1][1] + dy[D];
    }
    for(int i = 0; i < L; i++){
        if(nx == snake[i][0] && ny == snake[i][1]){
            return 1;
        }
    }
    return 0;
}

int getMinStep(int M, int N, int L, int K){
    Queue[tail].x = snake[0][0];
    Queue[tail].y = snake[0][1];
    Queue[tail].state = getState(L);
    Queue[tail].step = 0;
    visited[Queue[tail].x][Queue[tail].y][Queue[tail].state] = 1;
    if(Queue[tail].x == 1 && Queue[tail].y == 1) return 0;
    tail++;
    while(head < tail){
        Element curState = Queue[head++];
        //cout << "out " <<  curState.x << " " << curState.y << " " << curState.step << " " << curState.state << endl;
        for(int i = 0; i < 4; i++){
            int nx = curState.x + dx[i];
            int ny = curState.y + dy[i];
            int nd;
            if(i >= 2) nd = i - 2;
            else nd = i + 2;
            if(nx >= 1 && nx <= M && ny >= 1 && ny <= N){
                int mask = (1 << (2 * L - 2)) - 1;
                int nState = ((curState.state * 4) & mask) + nd;
                if(!visited[nx][ny][nState] && !isStone(nx, ny, K) && !isSnake(curState.x, curState.y, curState.state, L, nx, ny)){
                    Queue[tail].x = nx;
                    Queue[tail].y = ny;

                    Queue[tail].state = nState;
                    Queue[tail].step = curState.step + 1;

                    //cout << "in " <<  nx << " " << ny << " " << Queue[tail].step << " " << nState << endl;
                    if(nx == 1 && ny == 1) return Queue[tail].step;

                    tail++;
                    visited[nx][ny][nState] = 1;
                }
            }
        }
    }
    return -1;
}

int main(){
    //freopen("input.txt", "r", stdin);
    int nC = 1;
    while(1){
        int M, N, L;
        cin >> M >> N >> L;
        if(M + N + L == 0) break;

        for(int i = 0; i < L; i++){
            cin >> snake[i][0] >> snake[i][1];
        }
        int K;
        cin >> K;
        for(int i = 0; i < K; i++){
            cin >> stone[i][0] >> stone[i][1];
        }
        head = 0;
        tail = 0;
        for(int i = 0; i <= M; i++){
            for(int j = 0; j <= N; j++){
                for(int k = 0; k < SNAKE_STATES; k++){
                    visited[i][j][k] = 0;
                }
            }
        }
        int minStep = getMinStep(M, N, L, K);
        cout << "Case " << nC <<": "<< minStep << endl;
        nC++;
    }


    return 0;
}