priority

 kun倒是有一项特异功能——可以破坏障碍物。假设kun在一个N*M的迷宫中，"."代表可以通过的空地，"*"代表可以破坏的障碍物，"#"代表不可破坏的障碍物。问kun至少要使用多少次特异功能才可逃出迷宫？
"@"代表kun的位置。小昆虫每次可以向上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。

// priority_queue + bfs
#include
using namespace std;
const int Max = 1005;
int n, m;
char mp[Max][Max]{};
bool vis[Max][Max]{};
struct node{
    int x, y, num;
    friend bool operator < (const node&a,const node&b){
        return a.num > b.num;
    }
};
bool judge(int x,int y){
    if(x==1||x==n||y==1||y==m)
        return true;
    return false;
}
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool check(int x,int y){
    if(mp[x][y]=='#'||vis[x][y])
        return false;
    return true;
}
int bfs(int x,int y,int num){
    if(judge(x,y)){
        return 0;
    }
    priority_queue q;
    q.push({x, y, 0});
    vis[x][y] = true;
    while(!q.empty()){
        x = q.top().x;
        y = q.top().y;
        num = q.top().num;
        if(judge(x,y)){
            return num;
        }
        q.pop();
        for (int i = 0; i < 4;++i){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            // 能走
            if(check(dx,dy)){
                if(mp[dx][dy]=='*'){
                    q.push({dx, dy, num + 1});
                    //cout << dx << " " << dy << " " << num + 1 << endl;
                }
                else{
                    q.push({dx, dy, num});
                    //cout << dx << " " << dy << " " << num + 1 << endl;
                }
                vis[dx][dy] = true;
            }
        }
    }
    return -1;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        memset(vis, false, sizeof(vis));
        cin >> n >> m;
        int x, y;
        for (int i = 1; i <= n;++i)
            for (int j = 1; j <= m;++j){
                cin >> mp[i][j];
                if(mp[i][j]=='@'){
                    x = i, y = j;
                }
            }
        int ans = bfs(x, y, 0);
        cout << ans << endl;
    }
    //system("pause");
    return 0;
}