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
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define ll long long #define inf 0x3fffffff using namespace std; const int maxn = 105; struct Node { int x,y,step; friend bool operator <(Node a,Node b) { return a.step>b.step; } }; priority_queue<Node> q; int n,m; char a[maxn][maxn];//是char类型！！！ int vis[maxn][maxn]; int d[][2]={{1,0},{-1,0},{0,-1},{0,1}}; int ans; bool check(int x,int y) { if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || a[x][y]=='#')//“#”表示不能拆毁的障碍物！！！ return false; return true; } int bfs(int x1,int y1) { int ans=-1; while(!q.empty()) q.pop(); vis[x1][y1]=1; q.push( (Node){x1,y1,0} ); while(!q.empty()) { Node u=q.top(); q.pop(); if(u.x==0||u.x==n-1||u.y==0||u.y==m-1)//到达目标 //当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟 { ans=u.step; break; } for(int i=0;i<4;i++)//遍历4个方向 { int x=u.x+d[i][0]; int y=u.y+d[i][1]; if(check(x,y))//检查边界 { // vis[x][y]=1; if(a[x][y]=='.')//“.”表示可以直接通过的空地，“*”表示可以拆毁的障碍物 q.push(Node{x,y,u.step});//遇到空地不用付出步数 else q.push(Node{x,y,u.step+1}); vis[x][y]=1; } } } return ans;//如果不能逃离废墟，输出-1 return x } int main() { int t; scanf("%d",&t); int x1,y1,x2,y2; while(t--) { scanf("%d%d%",&n,&m); for(int i=0;i<n;i++) scanf("%s",&a[i]); memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='@')//“@”表示“猪坚强”的位置 { printf("%d ",bfs(i,j)); } } } } return 0; }