传送门：
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1726
1726: 你经历过绝望吗？两次！
Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 859 Solved: 290
Description
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
分析：
题目的衡量标准是拆除的障碍物的多少（可拆除的障碍物），而不是走的格子数目最少，
#include<stdio.h>
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
int t,n,m;
#define max_v 105
char G[max_v][max_v];
int vis[max_v][max_v];
int dir[][]={{-, }, {, }, {, -}, {, }};//方向引导数组
int step;
int sx,sy;//起始位置
struct node
{
int x,y,step;
bool operator < (const node & p) const{
return step > p.step;
}
};
int bfs()
{
memset(vis,,sizeof(vis));
priority_queue<node> q;
node p,next; p.x=sx;
p.y=sy;
p.step=; vis[sx][sy]=; q.push(p); while(!q.empty())
{
p=q.top();
q.pop();
step=p.step; if(p.x==||p.x==n-||p.y==||p.y==m-)//到达了废墟外围
{
return step;
} for(int i=;i<;i++)
{
next.x=p.x+dir[i][];
next.y=p.y+dir[i][];
next.step=; if(next.x>=&&next.x<n&&next.y>=&&next.y<m)//在废墟内（包括外围）
{
if(G[next.x][next.y]=='*')//可拆除障碍
{
next.step=step+;
}else if(G[next.x][next.y]=='.')//平路
{
next.step=step;
}else //if(G[next.x][next.y]=='#') //不可拆除的障碍
{
next.step=-;
}
if(next.step>=&&vis[next.x][next.y]==)//可通行且没有走过
{
vis[next.x][next.y]=;//标记
q.push(next);
}
}
}
}
return -;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
cin>>G[i][j];
if(G[i][j]=='@')//找起始位置
{
sx=i;
sy=j;
}
}
}
printf("%d\n",bfs());
}
return ;
}
所以定义结构体的时候加一个拆除障碍物的记录，为了能求出最少的，就使用优先队
列，其他的就跟普通的bfs模板题没有什么区别
注意没有固定的终点，只要求走到废墟外面！
code：