BFS简单练习

今天简单学习了一下BFS（宽度优先搜索），和昨天的DFS一样都是用来搜索。但是原理不太一样。DFS（运用递归）是不撞南墙不回头，BFS（队列）是一层一层遍历。

广度优先搜索核心代码

/** * 广度优先搜索 * @param Vs 起点 * @param Vd 终点 */ bool BFS(Node& Vs, Node& Vd){ queue<Node> Q; Node Vn, Vw; int i; //初始状态将起点放进队列Q Q.push(Vs); hash(Vw) = true;//设置节点已经访问过了！ while (!Q.empty()){//队列不为空，继续搜索！ //取出队列的头Vn Vn = Q.front(); //从队列中移除 Q.pop(); while(Vw = Vn通过某规则能够到达的节点){ if (Vw == Vd){//找到终点了！ //把路径记录，这里没给出解法 return true;//返回 } if (isValid(Vw) && !visit[Vw]){ //Vw是一个合法的节点并且为白色节点 Q.push(Vw);//加入队列Q hash(Vw) = true;//设置节点颜色 } } } return false;//无解 }

今天练习习题如下：

这道题就是BFS的基础运用，只要是能通过斜着的横着的竖着的连起来的就是一个油田，按照这个思想就能解出来。 代码如下：

#include<queue> #include<string.h> #include <iostream> #include<stdio.h> using namespace std; void BFS(int x,int y); int dx[8] = {-1,-1,-1,0,1,1,1,0}; int dy[8] = {-1,0,1,1,1,0,-1,-1}; int N,M; struct Node { int x,y; }; bool flag[105][105]; char a[105][105]; int main() { while(scanf("%d%d",&M,&N)&&M!=0) { memset(flag,0,sizeof(flag)); for(int i = 0;i < M;i++) for(int j = 0;j < N;j++) cin>>a[i][j]; int ans = 0; for(int i = 0;i < M;i++) for(int j = 0;j < N;j++) { if(flag[i][j] == 0 && a[i][j] == '@') { BFS(i,j); ans++; } } printf("%d\n",ans); } return 0; } void BFS(int x,int y) { flag[x][y] = 1; queue <Node> q; Node o,m; o.x = x,o.y = y; q.push(o);//添加新元素 while(!q.empty()) { o = q.front();//动态的记录压入的元素 q.pop();//删除第一个元素 for(int i = 0;i < 8;i++) { int xx = o.x + dx[i]; int yy = o.y + dy[i]; if(xx >= 0 && xx < M && yy >= 0 && yy < N && flag[xx][yy] == 0 && a[xx][yy] == '@') { flag[xx][yy] = 1; m.x = xx; m.y = yy; q.push(m); } } } }

这道题和第一题一样，用第一题的代码换一下字母就能解出来。 代码如下：

#include <iostream> #include<queue> #include<string.h> #include<stdio.h> using namespace std; int dx[8] = {-1,-1,-1,0,1,1,1,0}; int dy[8] = {-1,0,1,1,1,0,-1,-1}; void BFS(int x,int y); struct node { int x,y; }; bool flag[105][105]; int N,M,ans = 0; char a[105][105]; int main() { cin>>N>>M; memset(flag,0,sizeof(flag)); for(int i = 0;i < N;i++) for(int j = 0;j < M;j++) cin>>a[i][j]; for(int i = 0;i < N;i++) for(int j = 0;j < M;j++) { if(flag[i][j] == 0 && a[i][j] == 'W') { ans++; BFS(i,j); } } printf("%d\n",ans); return 0; } void BFS(int x,int y) { flag[x][y] = 1; queue <node> q; node o,m; o.x = x,o.y = y; q.push(o); while(!q.empty()) { o = q.front(); q.pop(); for(int i = 0;i < 8;i ++) { int xx = o.x + dx[i]; int yy = o.y + dy[i]; if(xx >= 0 && xx < N && yy >= 0 && yy < M && flag[xx][yy] == 0 && a[xx][yy] == 'W') { flag[xx][yy] = 1; m.x = xx; m.y = yy; q.push(m); } } } }

这道题和前几道类似，但是移动方式是上下左右，改过之后按照代码就能解出来。 代码如下：

#include <iostream> #include<string.h> #include<stdio.h> #include<queue> using namespace std; int dx[8] = {-1,0,1,0}; int dy[8] = {0,-1,0,1}; struct node { int x,y; }; void BFS(int x,int y,int ans); int H,W,ans; char a[25][25]; bool flag[25][25]; int main() { while(scanf("%d%d",&W,&H)&&H!=0&&W!=0) { ans = 1; memset(flag,0,sizeof(flag)); int startx,starty; for(int i = 0;i < H;i++) for(int j = 0;j < W;j++) { cin>>a[i][j]; if(a[i][j] == '@') { startx = i; starty = j; } } BFS(startx,starty,ans); } return 0; } void BFS(int x,int y,int ans) { flag[x][y] = 1; queue <node> q; node o,m; o.x = x,o.y = y; q.push(o); while(!q.empty()) { o = q.front(); q.pop(); for(int i = 0;i < 8;i++) { int xx = o.x + dx[i]; int yy = o.y + dy[i]; if(xx >= 0 && xx < H && yy >= 0 && yy < W && flag[xx][yy] == 0 && a[xx][yy] == '.') { ans++; flag[xx][yy] = 1; m.x = xx; m.y = yy; q.push(m); } } } printf("%d\n",ans); }

这道题今天让我懵了好久，一直想不太通怎么用BFS解，之后在网上百度了一下，看了一下其他大佬的代码，然后比葫芦画瓢写了一下，给的案例都能运行，但不知道为啥就是AC不了，真的是超级烦人。先把代码留下来。再看看。 代码如下：

#include <iostream> #include<stdio.h> #include<queue> #include<string.h> using namespace std; struct node { int x,step; }; void BFS(int x1,int x2); bool flag[100005]; int N,K; int main() { cin.tie(NULL);//解除cin与cout的绑定，进一步加快执行效率。 while(cin >> N >> K)//scanf("%d%d",&N,&K)) { // cin>>N>>K; memset(flag,0,sizeof(flag)); BFS(N,K); } return 0; } void BFS(int x1,int x2) { flag[x1] = 1; queue <node> q; node now,next; now.x = x1; now.step = 0; q.push(now); while(!q.empty()) { if(now.x == x2) { printf("%d\n",now.step); return ; //printf("%d\n",now.step); } now = q.front(); q.pop(); for(int i = 0;i < 3;i++) { if(i == 0) next.x = now.x + 1; else if(i == 1) next.x = now.x - 1; else if(i == 2) next.x = now.x * 2; if(next.x >= 0 && next.x <= 100000 && flag[next.x] == 0) { next.step = now.step + 1; flag[next.x] = 1; q.push(next); } } } }

这道题在做完前几道题后，自我感觉还是很简单的，但事实总是让人出乎意料，案列能完美运行，但就是不能AC，啊啊啊，真的是非常烦人，看了半天也找不到哪错了，先留着。 代码如下：

#include <iostream> #include<string.h> #include<stdio.h> #include<queue> using namespace std; int l,startx,starty,endx,endy; void BFS(int x,int y); struct node { int x,y,step; }; bool flag[305][305]; int dx[8] = {-1,-2,-2,-1,1,2,2,1}; int dy[8] = {-2,-1,1,2,2,1,-1,-2}; int main() { int N; scanf("%d",&N); while(N--) { memset(flag,0,sizeof(flag)); cin>>l>>startx>>starty>>endx>>endy; if(startx == endx && starty == endy) cout<<0<<endl; else BFS(startx,starty); } return 0; } void BFS(int x,int y) { flag[x][y] = 1; queue <node> q; node o,m; o.x = x; o.y = y; o.step = 0; q.push(o); while(!q.empty()) { if(o.x == endx && o.y == endy) { printf("%d\n",o.step); return; } o = q.front(); q.pop(); for(int i = 0;i < 8;i++) { int xx = o.x + dx[i]; int yy = o.y + dy[i]; if(xx >= 0 && xx < l && yy >= 0 && yy < l && flag[xx][yy] == 0) { flag[xx][yy] = 1; m.step = o.step + 1; m.x = xx; m.y = yy; q.push(m); } } } }