图的遍历——广度优先搜索
题目描述
广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点0出发，在访问了0之后依次从小到大访问各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算，输出遍历顶点的顺序。
注意：如果遍历一轮后没法再到达其他点，则程序结束。
输入描述
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。
输出描述
只有一行，包含n个整数，表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格
样例输入
4 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
样例输出
0 3 1 2
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,a[55][55],vis[2550],x;
queue<int> q;
void bfs(){
q.push(0);
vis[0]=1;
while(q.empty()==0){
x=q.front();
q.pop();
cout<<x<<" ";//遍历序列
for(int i=0;i<=n-1;i++){
if(a[x][i]==1&&vis[i]==0){
q.push(i);
vis[i]=1;
}
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
bfs();
return 0;
}关系网络
题目描述
有n个人，他们的编号为1~n，其中有一些人相互认识，现在x想要认识y，可以通过他所认识的人来认识更多的人（如果a认识b，b认识c，那么a可以通过b来认识c），求出x最少需要通过多少人才能认识y
输入描述
第一行3个整数n、x、y,2<=n<=100
接下来n行是一个nxn的邻接矩阵，a[i][j]=1表示i认识j，a[i][j]=0表示不认识。保证i=j时，a[i][j]=0,并且a[i][j]=a[j][i]
输出描述
一行一个整数，表示x认识y最少需要通过的人数。数据保证x一定能认识y
样例输入
5 1 5 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0
样例输出
2
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,x,y,a[105][105],vis[10005],t,step[105];
queue<int> q;
void bfs(){
q.push(x);
vis[x]=1;
while(q.empty()==0){
t=q.front();
q.pop();
if(t==y){
cout<<step[t]-1;
break;
}
for(int i=1;i<=n;i++){
if(a[t][i]==1&&vis[i]==0){
q.push(i);
vis[i]=1;
step[i]=step[t]+1;
}
}
}
}
int main(){
cin>>n>>x>>y;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
bfs();
return 0;
}走迷宫
输入描述
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用‘.’表示，有障碍物的格子用‘#’表示。
迷宫左上角和右下角都是‘.’。
输出描述
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
样例输入
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出
9
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,vis[45][45],x,y,step[45][45];
char a[45][45];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<int> qx,qy;
void bfs(){
qx.push(1);
qy.push(1);
vis[1][1]=1;
step[1][1]=1;
while(qx.empty()==0){
x=qx.front();
y=qy.front();
qx.pop();
qy.pop();
if(x==n&&y==m){
cout<<step[x][y];
return ;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&a[nx][ny]=='.'&&vis[nx][ny]==0){
qx.push(nx);
qy.push(ny);
vis[nx][ny]=1;
step[nx][ny]=step[x][y]+1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
bfs();
return 0;
}小可走迷宫
题目描述
小可置身于一个迷宫，每走一步只能向上下左右四个方向移动，请你帮小可找出从起点到终点的最短路程。
输入描述
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出描述
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
样例输入
1 5 5 S-### ----- ##--- E#--- ---##
样例输出
9
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,vis[105][105],x,y,r1,r,f,c1,c,t,step[105][105];
char a[105][105];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(){
queue<int> qx,qy;
qx.push(r);
qy.push(c);
vis[r][c]=1;
while(qx.empty()==0){
x=qx.front();
y=qy.front();
qx.pop();
qy.pop();
if(x==r1&&y==c1){
cout<<step[x][y]<<endl;
f=1;
break;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&a[nx][ny]!='#'&&vis[nx][ny]==0){
qx.push(nx);
qy.push(ny);
vis[nx][ny]=1;
step[nx][ny]=step[x][y]+1;
}
}
}
}
int main(){
cin>>t;
while(t--){
memset(vis,0,sizeof vis);
memset(step,0,sizeof step);
f=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='S'){
r=i;
c=j;
}
if(a[i][j]=='E'){
r1=i;
c1=j;
}
}
}
bfs();
if(f==0){
cout<<-1<<endl;
}
}
return 0;
}迷宫
题目描述
一天小可在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当小可处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，小可想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
输入描述
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出描述
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,vis[105][105],x,y,r1,r,f,c1,c,t,step[105][105];
char a[105][105];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(){
queue<int> qx,qy;
qx.push(r);
qy.push(c);
vis[r][c]=1;
while(qx.empty()==0){
x=qx.front();
y=qy.front();
qx.pop();
qy.pop();
if(x==r1&&y==c1){
f=1;
break;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<n&&nx>=0&&ny<n&&ny>=0&&a[nx][ny]!='#'&&vis[nx][ny]==0){
qx.push(nx);
qy.push(ny);
vis[nx][ny]=1;
step[nx][ny]=step[x][y]+1;
}
}
}
}
int main(){
cin>>t;
while(t--){
memset(vis,0,sizeof vis);
memset(step,0,sizeof step);
f=0;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
cin>>r>>c>>r1>>c1;
bfs();
if(f==1){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}奇怪的电梯
题目描述
假设一栋大楼有一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼（1<=i<=N）上有一个数字Ki（0<=Ki<=N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki（K1=3，K2=3，……），从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入描述
第1行为3个正整数，表示N,A和B，1<=N<=200，1<=A,B<=N;
第2行为N个正整数，表示Ki。
输出描述
一行，共一个数，即最少按键次数。若无法到达，则输出-1。
样例输入
5 1 5 3 3 1 2 5
样例输出
3
代码
(用邻接矩阵求解)
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int a[205][205];
int n,A,B,x,vis[40005],step[205];
queue<int>q;
void bfs(){
q.push(A);
vis[A]=1;
while(q.empty()==0){
int x=q.front();
q.pop();
if(x==B){
cout<<step[x];
return ;
}
for(int i=1;i<=n;i++){
if(a[x][i]==1&&vis[i]==0){
q.push(i);
vis[i]=1;
step[i]=step[x]+1;
}
}
}
cout<<-1;
}
int main(){
cin>>n>>A>>B;
for(int i=1;i<=n;i++){
cin>>x;
if(i+x<=n){
a[i][i+x]=1;
}
if(i-x>=1){
a[i][i-x]=1;
}
}
bfs();
return 0;
}