学步园

这道题贡献了2次wa，最后原因是因为A有100个，而S有一个，所以共有101个点，数组应该开到102，而我只开到了101...........坑爹啊

code

/*
ID: yueqiq
PROG: numtri
LANG: C++
*/
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 102;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
//此题为判断负权回路
int N,M,W,v_cnt,e_cnt,dis[maxn];
char maze[maxn][maxn];
int edge[maxn][maxn];
bool vis[maxn][maxn];//bfs
bool use[maxn];//prim
struct node{
    int x,y,step;
}V[maxn];
void bfs(){
    node cur,tmp;
    FOR(i,1,v_cnt){
        edge[i][i]=0;
        FOR(j,i+1,v_cnt){
            edge[i][j]=edge[j][i]=INF;
        }
    }
    FOR(i,1,v_cnt){
        queue<node> q;
        SET(vis,false);
        cur=V[i];
        cur.step=0;
        vis[cur.x][cur.y]=1;
        q.push(cur);
        //printf("x:%d y:%d\n",cur.x,cur.y);
        while(!q.empty()){
            tmp=q.front();
            q.pop();
            //printf("poper x:%d y:%d step:%d\n",tmp.x,tmp.y,tmp.step);
            FOR(j,i+1,v_cnt){
                if(tmp.x==V[j].x && tmp.y==V[j].y){
                    edge[i][j]=edge[j][i]=tmp.step;
                }
            }
            FF(j,4){
                int nx=tmp.x+dx[j];
                int ny=tmp.y+dy[j];
                //printf("nx %d  ny%d\n",nx,ny);
                if(nx<1||ny<1||nx>N||ny>M) continue;
                if(vis[nx][ny]) continue;
                if(maze[nx][ny]=='#') continue;
                cur.x=nx;cur.y=ny;cur.step=tmp.step+1;
                vis[nx][ny]=1;
                //printf("enter x:%d y:%d step:%d\n",cur.x,cur.y,cur.step);
                q.push(cur);
            }
        }
        //puts("end!-------------------------");
    }
}
int prim(){
    SET(use,false);
    int ans=0,minn;
    int s=1;
    use[s]=true;
    FOR(i,1,v_cnt) dis[i]=edge[s][i];
    FOR(i,1,v_cnt-1){
        minn=INF;
        FOR(j,1,v_cnt){
            if(!use[j] && dis[j]<minn){
                minn=dis[j];
                s=j;
            }
        }
        ans+=minn;
        use[s]=true;
        FOR(j,1,v_cnt){
            if(!use[j] && dis[j] > edge[s][j]){
                dis[j]=edge[s][j];
            }
        }
    }
    return ans;
}
void readGraph(){
    e_cnt=1;
    v_cnt=1;
    scanf("%d%d%d",&M,&N);
//    char t[51];
//    gets(t);
    FOR(i,1,N){
        gets(maze[i]);
        FOD(j,M,1){
            maze[i][j]=maze[i][j-1];
            if(maze[i][j]=='A'||maze[i][j]=='S'){
                V[v_cnt].x=i;
                V[v_cnt++].y=j;
            }
        }
    }
    v_cnt--;
//    FOR(i,1,N){
//        FOR(j,1,M){
//            printf("%c",maze[i][j]);
//        }
//        LN;
//    }
}
int main()
{
    int cas;
    SD(cas);
    while(cas--){
        readGraph();
        bfs();
//        FOR(i,1,v_cnt){
//            printf("i:%d x:%d y:%d\n",i,V[i].x,V[i].y);
//        }
//        FOR(i,1,v_cnt) FOR(j,i+1,v_cnt){
//            printf("edge[%d][%d]==%d\n",i,j,edge[i][j]);
//        }
        PD(prim());LN;
    }
    return 0;
}