练习1.
在这里插入代码片#include<bits/stdc++.h>using namespace std;struct point/*定义一个结构体表示队列里面的三种元素*/{int x;int y;int step;}; /*规定地图以外的区域用0表示，可以行走的区域用1表示 2来表示障碍物（不可以行走的）的区域*/int n,a[110][110],b[110][110]; /*地图的大小、储存地图，记录哪些位置走过哪些没走过 */ queue<point>q;//定义队列 /*51 1 2 1 11 1 2 2 21 2 1 2 21 1 1 1 11 2 1 2 18*/ int main(){cin>>n;for(int i=1;i<=n;i++)//构建地图 {for(int j=1;j<=n;j++){cin>>a[i][j];}}/*BFS*/point start = {1,1,0},temp;//第一行第一列是0步,所以一步都不用走 q.push(start);while(q.empty()==0)/*队列为空时结束,不为空就进行搜索(队列为空时返回true,为0时说明队列不为空),往四个方向试探的走一走*/{int x = q.front().x;//返回队头元素中行的下标 int y=q.front().y;//返回队头元素中列的下标 int step = q.front().step; /*拿出队头元素中走到这一步所需的步数*/if(x==n&&y==n)//如果已经到达了目标地点就输出到大目标点所需要的步骤并结束。 {cout<<step;break;}/*上*/if(a[x-1][y]==1&&b[x-1][y]==0)//上面的位置等于1表示是可走的区域，同时这个位置的标记为0表示还没有走过就可以走了，此时就可以入队了{temp.x = x-1;//新的行的下标 temp.y = y;//新的列的下标 temp.step = step + 1;//每走一步，步数加1 q.push(temp);//入队b[x-1][y] = 1;//入队以后就表示走过了，走过了就将它赋值为1表示走过。} /*下*/if(a[x+1][y]==1&&b[x+1][y]==0)//上面的位置等于1才可以走，同时这个位置还没有走过就可以放入队列中去 {temp.x = x+1;temp.y = y;temp.step = step + 1;q.push(temp);//入队以后就表示走过了，走过了就将它赋值为1表示走过。 b[x+1][y] = 1;} /*左*/if(a[x][y-1]==1&&b[x][y-1]==0) {temp.x = x;temp.y = y-1;temp.step = step+1;q.push(temp);b[x][y-1]=1;}/*右*/if(a[x][y+1]==1&&b[x][y+1]==0){temp.x = x;temp.y = y+1;temp.step = step+1;q.push(temp);b[x][y+1]=1;}q.pop();//如果上下左右都不能走就要删除队头元素。 }return 0;}
练习2.
/*最短路径问题：从A城市出发到大目标城市求最短的路线：解题思路：首先使用数组a记录途径城市，用数组b记录所经过的城市，数组c记录哪些城市走过哪些没走过每当a记录一次所经的城市时，数组b都会将该城市的前驱城市记录下来...当找到目标城市时，最短路线就已经储存在b数组中了。逆序输出一下b数组就是我们所要的答案。 */ #include<bits/stdc++.h>using namespace std;//使用邻接矩阵来表示城市，只有8个城市所以需要开辟8*8的二维数组，在这里不使用第0行和第0列所以开9*9的 int city[9][9]={{0,0,0,0,0,0,0,0,0},{0,1,0,0,0,1,0,1,1},{0,0,1,1,1,1,0,1,1},{0,0,1,1,0,0,1,1,1}, {0,0,1,0,1,1,1,0,1},{0,1,1,0,1,1,1,0,0}, {0,0,0,1,1,1,1,1,0},{0,1,1,1,0,0,1,1,0},{0,1,1,1,1,0,0,0,1}};int a[101];//记录途径城市 int b[101];//记录途径城市的前驱城市 int c[9];//标记哪些城市走过了避免重复走 //输出函数out，用来逆序输出b城市中保存的前驱城市 void out(int d)//传进来储存前驱城市的b数组的下标，该下标对应着前驱城市的下标将它在a数组里输出即可 {cout<<char(a[d]+64 );//a[8]=8,8+64==72 ->'H'; while(b[d]!=0)//b数组里面记录着每个前驱城市，第一个是A的前驱城市0，所以当b数组中的元素为0时说明b数组已经逆序输出完毕 {d = b[d]; //注意该语句就是该循环的循环变量自减。 cout<<"--"<<char(a[d]+64);}} //编写宽搜函数 void bfs(){//初始化int head=0,tail=1; //定义队头，队尾a[1]=1;//将起始城市入队b[1]=0;//A城没有前驱城市所以是0c[1]=1;//A城走过了do{head++;//队头++搜索新的城市for(int i=1;i<=8;i++)//按照遍历规则能够遍历的方法数目：A->A,A->B,A->c,A->d,A->E,A->F,A->H; (搜索每一层,搜索每一个城市){if(city[head][i]==0&&c[i]==0)//如果该城市能走(能直通且没走过)就将它入队。{tail++;//队尾加1,将新的城市入队a[tail]=i;//入队b[tail]=head;//记录每个城市的前驱城市（B，C，D，F的前驱城市就是A邻接矩阵中用1表示A,所以将1入队） c[i]=1;//标记每一个走过的城市if(i==8)//如果入队的是第8个城市H，说明我们找到的目标城市，此时只需要逆序输出储存在b城市中的城市即可得到最短路线：H--F--A {out(tail);//逆序输出b城市中保存的前驱城市 break; } } } }while(head<tail);//当遍历完全部结点时停止搜索 } int main(){bfs(); return 0;}
