（2016弱小联盟十一专场10.3） Help the Princess! BFS

本文主要是介绍（2016弱小联盟十一专场10.3） Help the Princess! BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：
https://acm.bnu.edu.cn/v3/statments/jag2016.pdf

分析：

直接判断‘%’到‘@’和最近的‘$’的距离，如果 ‘%’到‘@’小于%’到最近的‘$’的距离则输出YES否则输出NO

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;const int maxn = 210;
char mmap[maxn][maxn];
int h,w;
int ansp,anss;
int dir[2][4] = {0,0,1,-1,1,-1,0,0};
bool vis[maxn][maxn];struct node
{int x,y,step;
};void bfs(int x,int y)
{memset(vis,false,sizeof(vis));queue<node> q;node now,ne;now.x = x; now.y = y; now.step = 0;q.push(now);vis[x][y] = true;while(!q.empty()){now = q.front();q.pop();for(int i=0;i<4;i++){ne.x = now.x + dir[0][i];ne.y = now.y + dir[1][i];if(!vis[ne.x][ne.y] && ne.x >= 1 && ne.x <= h && ne.y >= 1 && ne.y <= w && mmap[ne.x][ne.y]!='#'){ne.step = now.step + 1;vis[ne.x][ne.y] = true;if(mmap[ne.x][ne.y] == '@')ansp = min(ne.step,ansp);else if(mmap[ne.x][ne.y] == '$')anss = min(ne.step,anss);q.push(ne);}}if(ansp < 9999999 && anss < 9999999) break;}}
int main()
{while(scanf("%d%d",&h,&w)!=EOF){int x,y;ansp = anss = 9999999;getchar();for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){scanf("%c",&mmap[i][j]);if(mmap[i][j] == '%'){x = i; y = j;}}getchar();}bfs(x,y);if(ansp < anss) printf("Yes\n");else printf("No\n");}return 0;
}

这篇关于（2016弱小联盟十一专场10.3） Help the Princess! BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---