c++佚名者学校根据c++编程开了很多课程。
这是一个阳光明媚的日子。清风轻抚大地，划过河岸，嬉戏在柳树间。小航离开宿舍，在春光的沐浴中走向“算法教室”。
算法课由XC老师开展教授。“叮——叮——”上课铃响了，GDN老师走入教室，“废话不说，上课！”
第一部分：认识BFS
“同学们对基础算法之一——DFS掌握的还挺好的，今天我们就学习BFS，就是宽度优先搜索！请同学们认真听课！”GDN老师扫视着同学们。
“BFS属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。”GDN老师看着认真认真听讲的同学们，“通过你们现在看到的程序，我们可以认识到它的搜索流程”
编辑
“好了，话说‘时间是验证真理的一个重要环节’（我瞎编的），我们现在就来做题吧！请看题”
第二部分：做题
1.红与黑
总时间限制: 1000ms 内存限制: 65536kB
描述：
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，
计算你总共能够到达多少块黑色的瓷砖。
输入：
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向
瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示
一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
输出：
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始
位置的瓷砖)。
样例输入：
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
样例输出：
45
“这是一道非常经典的搜索题”GDN老师说。
#include<iostream> #include<queue> using namespace std; char room[23][23]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; //四个方向 int wx,hy,num; #define CHECK(x,y) (x<wx&&x>=0&&y>=0&&y<hy)//是否在room中 //define 是定义 + 大写变量/方法 struct node{ int x,y; };//结构体 void BFS(int dx,int dy) { num=1; queue<node>q; //定义一个node型的队列q node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty())//= {q.empty()==0} { start=q.front(); q.pop(); for(int i=0;i<4;i++) { next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(CHECK(next.x,next.y)&&room[next.x][next.y]=='.') //判断是否可走 { num++; room[next.x][next.y]='#'; q.push(next); } } } } int main() { int x,y,dx,dy; while(cin>>wx>>hy) //多组输入 { if(wx==0&&hy==0) break;//结束多组输入 for(y=0;y<hy;y++) { for(x=0;x<wx;x++) { cin>>room[x][y]; if(room[x][y]=='@') //起点 { dx=x; dy=y; } } } num=0; BFS(dx,dy); cout<<num<<endl; } return 0; }
2.【宽度优先搜索BFS】面积
(File IO): input:area.in output:area.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10*10的二维数组中，有“*”围住了15个点，因此面积为15。
编辑
输入：
如上
输出：
如上
样例输入：
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
样例输出：
15
include<cstdio> using namespace std; int n,m,a[15][15],b[15][15],de[1005][2],i,j=1,k; int main() { freopen("area.in","r",stdin); freopen("area.out","w",stdout); for(int ii=1;ii<=10;ii++) for(int jj=1;jj<=10;jj++) { scanf("%d",&a[ii][jj]); if(a[ii][jj]==1) k++; } if(k==0) { printf("100"); return 0; } de[1][1]=0; de[1][2]=0; b[0][0]=1; a[0][0]=1; k=0; while(i<j) { i++; for(int i1=-1;i1<=1;i1++) { if(i1==0) continue; if(de[i][1]+i1>=0&&de[i][1]+i1<=11&&a[de[i][1]+i1][de[i][2]]==0&&b[de[i][1]+i1][de[i][2]]==0) { j++; de[j][1]=de[i][1]+i1; de[j][2]=de[i][2]; a[de[j][1]][de[j][2]]=1; b[de[j][1]][de[j][2]]=1; } } for(int i1=-1;i1<=1;i1++) { if(i1==0) continue; if(de[i][2]+i1>=0&&de[i][2]+i1<=11&&a[de[i][1]][de[i][2]+i1]==0&&b[de[i][1]][de[i][2]+i1]==0) { j++; de[j][1]=de[i][1]; de[j][2]=de[i][2]+i1; a[de[j][1]][de[j][2]]=1; b[de[j][1]][de[j][2]]=1; } } } for(int i1=1;i1<=10;i1++) { for(int j1=1;j1<=10;j1++) { if(a[i1][j1]==0) k++; } } printf("%d",k); fclose(stdin); fclose(stdout); return 0; }
3.【宽度优先搜索BFS】细胞
(File IO): input:cell.in output:cell.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
一个矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。如：
阵列：
4 10
0234500067
1034560500
2045600671
0000000089
e有4个细胞。
输入:
如题
输出:
如题
样例输入:
4 10
0234500067
1034560500
2045600671
0000000089
样例输出:
4
#include<bits/stdc++.h> using namespace std; struct zuobiao { int x,y; }; queue<zuobiao>q; zuobiao c; int sum,n,m,fang[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; char ma[105][105]; int visit[105][105]; void bfs(int x,int y) { sum++; c.x=x; c.y=y; q.push(c); visit[c.x][c.y]=1; while(!q.empty()) { zuobiao t=q.front(),ne; q.pop(); for(int i=0;i<4;i++) { ne.x=t.x+fang[i][0]; ne.y=t.y+fang[i][1]; if(ne.x<=n&&ne.x>=1&&ne.y<=m&&ne.y>=1&&ma[ne.x][ne.y]!='0'&&visit[ne.x][ne.y]==0) { q.push(ne); visit[ne.x][ne.y]=1; } } } } int main() { freopen("cell.in","r",stdin); freopen("cell.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>ma[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(visit[i][j]==0&&ma[i][j]!='0') { bfs(i,j); } } } cout<<sum; fclose(stdin); fclose(stdout); }
第三部分：总结
“触及算法的问题没有具体的做法，需要慢慢摸索、探求规律、多练多做，才能真正掌握！”GDN老师一脸严肃地望着同学们……
参考资料：
宽度优先搜索（百度百科）：宽度优先搜索_百度百科 (baidu.com)
题目选自：Gold Medal Online Judge System (gmoj.net)中的若干算法题
