CSU 1726: 你經曆過絕望嗎？兩次！

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;

const int maxn=110;

char ch[maxn][maxn];
int num[maxn][maxn];
bool user[maxn][maxn];
int tox[4]={1,0,0,-1};
int toy[4]={0,1,-1,0};
int n,m;

struct Node{
  
  int x,y,cnt;
  Node(int x_,int y_,int cnt_):x(x_),y(y_),cnt(cnt_){}
  bool operator <(const Node &x) const{
     
     return cnt>x.cnt;
  }
};

int BFS(int x,int y){
  
  priority_queue<Node>que;
  que.push(Node(x,y,0));
  while(!que.empty()){
    
    Node node=que.top();
    que.pop();
    int indx=node.x,indy=node.y;
    if(indx==0 || indx==n-1 || indy==0 || indy==m-1) return node.cnt;
    for(int i=0;i<4;i++){
      
      int newx=indx+tox[i],newy=indy+toy[i];
      if(newx<0 || newx>=n || newy<0 || newy>=m || num[newx][newy]==-1) continue;
      if(user[newx][newy]) continue;
      int newcnt=node.cnt+num[newx][newy];
      user[newx][newy]=true;
      que.push(Node(newx,newy,newcnt));
    }
  }
  return -1;
}

int main(){
  
  int T;
  scanf("%d",&T);
  while(T--){
    
    scanf("%d%d",&n,&m);
    int startx,starty;
    for(int i=0;i<n;i++){
      
      for(int j=0;j<m;j++){
        
        cin>>ch[i][j];
        if(ch[i][j]=='.') num[i][j]=0;
        else if(ch[i][j]=='#') num[i][j]=-1;
        else if(ch[i][j]=='*') num[i][j]=1;
        else startx=i,starty=j;
        user[i][j]=false;
      }
    }
    user[startx][starty]=true;
    int key=BFS(startx,starty);
    printf("%d\n",key);
  }
}