首页 > 其他 > 详细

bfs——Red and Black

时间:2020-01-20 00:48:54      阅读:110      评论:0      收藏:0      [点我收藏+]

A - Red and Black

 

 1 #include<bits/stdc++.h>
 2 using  namespace std;
 3 const int maxn=25;
 4 int n;int m;
 5 int x;int y;int ans;
 6 char s[maxn][maxn];//输入迷宫 
 7 int ah[maxn][maxn];//用ah数组标记是否走过,0代表没走过,1代表走过 
 8 struct node{
 9     int x;int y;
10 }st;
11 int movede[4][2]={ {1 ,0},{-1 , 0},{0 , 1},{0 ,-1} };//代表移动 
12 bool ok(int fx,int fy){//用ok数组代表该点是否能走,若能走则返回true,否则返回false 
13     if(fx<1||fx>m||fy<1||fy>n)return false;//该判断是用来判断该点是否在迷宫外 
14 //    else if(s[fx][fy]==‘@‘)return false;//该判断是用来判断该点是否为起点 ; 
15 //    else if(s[fx][fy]==‘#‘)return false; //该判断是用来判断该点是否为障碍;
16     //上面两判断能用 
17     else if(s[fx][fy]!=.)return false;
18     //来代替; 
19     else if(s[fx][fy]==.&&ah[fx][fy]==1)return false;//该判断是用来判断点是否走过; ah[fx][fy]=1时代表走过 
20     else if(s[fx][fy]==.&&ah[fx][fy]==0)return true;//ah【fx】【fy】=0时代表没走过 
21 }
22 void bfs(){//搜索函数 
23     ah[st.x][st.y]=1; 
24     queue<node>q;//创建队列q; 
25     q.push(st);//将起点放入q这个队列中 
26     while(!q.empty()){//当q这个队列空的话,就代表无路可走,那么跳出循环 
27         ans++;
28         node t=q.front();//记录队列中排第一个点 
29         q.pop();//扔掉队列中第一个点 
30         node newnode;//记录下一个能走的点 
31         for(int i=0;i<4;i++){//寻找下一个能走的点 
32             int fx=t.x+movede[i][0];
33             int fy=t.y+movede[i][1];
34             if(ok(fx,fy)){//若ok返回true,这个点代表能走。就将fx,fy放入newnode 
35                 newnode.x=fx;
36                 newnode.y=fy;
37                 ah[fx][fy]=1;
38                 q.push(newnode);//然后将newnode放入队列q中 
39             }
40         }
41     }
42 }
43 int main(){
44     while(scanf("%d%d",&n,&m)!=EOF){
45         if(n==0&&m==0)break;
46         memset(ah,0,sizeof ah);//使ah数组全为0,开始搜索 
47         for(int i=1;i<=m;i++){
48             scanf("%s",s[i]+1);//输入迷宫,由于循环是从1开始的,所以s[i]输入时要加1; 
49         }
50         for(int i=1;i<=m;i++){//用来寻找出发点 
51             for(int j=1;j<=n;j++){
52                 if(s[i][j]==@){
53                     st.x=i;st.y=j;break;//当找到出发点这跳出循环; 
54                 }
55             }
56         }
57         ans=0;//ans代表能走个数。该处等于0,给其初始化,进行下一组搜索 
58         bfs();//广度优先搜索,来搜索能走个数 
59         printf("%d\n",ans);
60     }
61 }

这道题题意是在一房间中。一个人站在一块黑色瓷砖“@”上,他可以移动到四个相邻的瓷砖之一。但他不能在红色瓷砖“#”上移动,只能在黑色瓷砖“.”上移动。让我们求他最大能走的砖数。

这道题用到了bfs(广度优先搜索),遍历图,去寻找能走的黑色瓷砖“.”数。

这题可作为做bfs这类题的模板。

bfs——Red and Black

原文:https://www.cnblogs.com/kitalekita/p/12215993.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!