本文主要是介绍CSU 1726: 你经历过绝望吗？两次！ BFS,优先队列求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1726: 你经历过绝望吗？两次！
Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 507 Solved: 162Description
4月16日，日本熊本地区强震后，受灾严重的阿苏市一养猪场倒塌，幸运的是，猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困的“猪坚强”。不过与在废墟中靠吃木炭饮雨水存活36天的中国汶川“猪坚强”相比，熊本的猪可没那么幸运，因为它们最终还是没能逃过被送往屠宰场的命运。
我们假设“猪坚强”被困在一个N*M的废墟中，其中“@”表示“猪坚强”的位置，“.”表示可以直接通过的空地，“#”表示不能拆毁的障碍物，“*”表示可以拆毁的障碍物，那么请问消防员至少要拆毁多少个障碍物，才能从废墟中救出“猪坚强”送往屠宰场？（当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟）
Input
多组数据，第一行有一个整数T，表示有T组数据。（T<=100）
以下每组数据第一行有两个整数N和M。(1<=N,M<=100)
接着N行，每行有一个长度为M的字符串。
Output
一个整数，为最少拆毁的障碍物数量,如果不能逃离废墟，输出-1。
Sample Input
3 3 3 ### #@* *** 3 4 #### #@.* **.* 3 3 .#. #@# .#.
Sample Output
1 0 -1
Hint
Source
中南大学第十届大学生程序设计竞赛
Author
LVV
很明显的含有障碍物的迷宫问题，所以我们直接用优先队列做BFS直接就能求解了，优先队列中我们按照step步数设置优先级，'.'的代价为0，'\*'的代价为1，只要走到边界就输出对应的值
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>const double eps=1e-8;
const double PI=acos(-1.0);
using namespace std;struct Node
{int x,y,step;friend bool operator <(Node a,Node b){return a.step>b.step;}
} node;int ans;
int c[][2]= {{1,0},{-1,0},{0,1},{0,-1}};
char a[105][105];
int n,m,a1,a2,n1,n2;
void bfs(int i,int j)
{//memset(vis,0,sizeof(vis));priority_queue<Node> q;node.x=i;node.y=j;node.step=0;a[i][j]='#';q.push(node);while(!q.empty()){Node temp,tp=q.top();q.pop();if(tp.x==n-1||tp.y==m-1||tp.x<=0||tp.y<=0){ans=tp.step;return ;}for(int k=0; k<4; k++){temp.x=tp.x+c[k][0];temp.y=tp.y+c[k][1];if(temp.x<n&&temp.y<m&&temp.x>=0&&temp.y>=0&&a[temp.x][temp.y]!='#'){if(a[temp.x][temp.y]=='*')temp.step=tp.step+1;elsetemp.step=tp.step;q.push(temp);a[temp.x][temp.y]='#';}}}ans=-1;
}int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0; i<n; i++)//这里用字符串输入最好，用%c一个一个字符输入的时候OJ判WA，也不清楚为啥{scanf("%s",a[i]);}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(a[i][j]=='@'){a1=i;a2=j;break;}}ans=0;bfs(a1,a2);printf("%d\n",ans);memset(a,0,sizeof(a));}return 0;
}
这篇关于CSU 1726: 你经历过绝望吗？两次！ BFS,优先队列求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
