4月16日，日本熊本地区强震后，受灾严重的阿苏市一养猪场倒塌，幸运的是，猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困的“猪坚强”。不过与在废墟中靠吃木炭饮雨水存活36天的中国汶川“猪坚强”相比，熊本的猪可没那么幸运，因为它们最终还是没能逃过被送往屠宰场的命运。

 

我们假设“猪坚强”被困在一个N*M的废墟中，其中“@”表示“猪坚强”的位置，“.”表示可以直接通过的空地，“#”表示不能拆毁的障碍物，“*”表示可以拆毁的障碍物，那么请问消防员至少要拆毁多少个障碍物，才能从废墟中救出“猪坚强”送往屠宰场？（当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟）

 

多组数据，第一行有一个整数T，表示有T组数据。（T<=100）

以下每组数据第一行有两个整数N和M。(1<=N,M<=100)

接着N行，每行有一个长度为M的字符串。

#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 ;

}