- A - Red and Black https://vjudge.net/problem/HDU-1312
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=25;
- int n;int m;
- int x;int y;int ans;
- char s[maxn][maxn];// 输入迷宫
- int ah[maxn][maxn];// 用 ah 数组标记是否走过, 0 代表没走过, 1 代表走过
- struct node{
- int x;int y;
- }st;
- int movede[4][2]={ {1 ,0},{-1 , 0},{0 , 1},{0 ,-1} };// 代表移动
- bool ok(int fx,int fy){// 用 ok 数组代表该点是否能走, 若能走则返回 true, 否则返回 false
- if(fx<1||fx>m||fy<1||fy>n)return false;// 该判断是用来判断该点是否在迷宫外
- // else if(s[fx][fy]=='@')return false;// 该判断是用来判断该点是否为起点 ;
- // else if(s[fx][fy]=='#')return false; // 该判断是用来判断该点是否为障碍;
- // 上面两判断能用
- else if(s[fx][fy]!='.')return false;
- // 来代替;
- else if(s[fx][fy]=='.'&&ah[fx][fy]==1)return false;// 该判断是用来判断点是否走过; ah[fx][fy]=1 时代表走过
- else if(s[fx][fy]=='.'&&ah[fx][fy]==0)return true;//ah[fx] [fy] =0 时代表没走过
- }
- void bfs(){// 搜索函数
- ah[st.x][st.y]=1;
- queue<node>q;// 创建队列 q;
- q.push(st);// 将起点放入 q 这个队列中
- while(!q.empty()){// 当 q 这个队列空的话, 就代表无路可走, 那么跳出循环
- ans++;
- node t=q.front();// 记录队列中排第一个点
- q.pop();// 扔掉队列中第一个点
- node newnode;// 记录下一个能走的点
- for(int i=0;i<4;i++){// 寻找下一个能走的点
- int fx=t.x+movede[i][0];
- int fy=t.y+movede[i][1];
- if(ok(fx,fy)){// 若 ok 返回 true, 这个点代表能走. 就将 fx,fy 放入 newnode
- newnode.x=fx;
- newnode.y=fy;
- ah[fx][fy]=1;
- q.push(newnode);// 然后将 newnode 放入队列 q 中
- }
- }
- }
- }
- int main(){
- while(scanf("%d%d",&n,&m)!=EOF){
- if(n==0&&m==0)break;
- memset(ah,0,sizeof ah);// 使 ah 数组全为 0, 开始搜索
- for(int i=1;i<=m;i++){
- scanf("%s",s[i]+1);// 输入迷宫, 由于循环是从 1 开始的, 所以 s[i] 输入时要加 1;
- }
- for(int i=1;i<=m;i++){// 用来寻找出发点
- for(int j=1;j<=n;j++){
- if(s[i][j]=='@'){
- st.x=i;st.y=j;break;// 当找到出发点这跳出循环;
- }
- }
- }
- ans=0;//ans 代表能走个数. 该处等于 0, 给其初始化, 进行下一组搜索
- bfs();// 广度优先搜索, 来搜索能走个数
- printf("%d\n",ans);
- }
- }
这道题题意是在一房间中. 一个人站在一块黑色瓷砖 "@" 上, 他可以移动到四个相邻的瓷砖之一. 但他不能在红色瓷砖 "#" 上移动, 只能在黑色瓷砖 "." 上移动. 让我们求他最大能走的砖数.
这道题用到了 bfs(广度优先搜索), 遍历图, 去寻找能走的黑色瓷砖 "." 数.
这题可作为做 bfs 这类题的模板.
来源: http://www.bubuko.com/infodetail-3388896.html