第一次贴代码 纪念一下
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<string>
#include<queue>
#define INF 999999
using namespace std;
typedef class{
public:
	int h;
	int w;
	int step;
}V;
V vex[110];
int adj[110][110];
char map[60][60];
char vexid[110][110];
char visit[110][110];
int d[110];
void dfs(V start,int h,int w,int id){
	queue<V> q;
	q.push(start);
	while (!q.empty()){
		V vtmp1=q.front(), vtmp2;
		q.pop();
		for (int i = 0; i < 4; i++){
			vtmp2 = vtmp1;
			switch (i){
			case 0: vtmp2.h = vtmp1.h+1; break;
			case 1: vtmp2.h = vtmp1.h-1; break;
			case 2: vtmp2.w = vtmp1.w+1; break;
			case 3: vtmp2.w = vtmp1.w-1; break;
			}
			if (vtmp2.h>0 && vtmp2.h<h &&vtmp2.w>0 && vtmp2.w < w&&map[vtmp2.h][vtmp2.w] != '#' && !visit[vtmp2.h][vtmp2.w]){
				vtmp2.step++;
				visit[vtmp2.h][vtmp2.w] = 1;
				if (map[vtmp2.h][vtmp2.w] != ' '){
					adj[id][vexid[vtmp2.h][vtmp2.w]] = vtmp2.step;
				}
				q.push(vtmp2);
			}
		}
	}
}
void prim(int vexnum){
	//初始化
	for (int i = 1; i < vexnum; i++){
		d[i] = adj[0][i];
	}
	d[0] = 0;
	int result = 0;
	for (int i = 1; i < vexnum; i++){
		int min = INF;
		int vtmp = -1;
		for (int i = 1; i < vexnum; i++){
			if (min>d[i] && d[i] != 0){
				min = d[i];
				vtmp = i;
			}
		}

		if (vtmp == -1 || min == INF){ break; }
		result += min;
		d[vtmp] = 0;
		//更新
		for (int i = 0; i < vexnum; i++){
			if (adj[i][vtmp] < d[i]){
				d[i] = adj[i][vtmp];
			}
		}
	}
	cout << result << endl;
}
int main(){
	char c, b[100];
	int N;
	gets(b);
	sscanf(b, "%d", &N);
	while (N--){
		//各种初始化
		memset(map, 0, 60 * 60);
		memset(vex, 0, 110 * sizeof(V));
		memset(vexid, -1, 110);
		memset(adj, 0, 110 * 100 * sizeof(int));
		//输入数据
		int w, h, vexnum = 0;
		gets(b);
		sscanf(b, "%d %d", &w, &h);
		for (int i = 0; i < h; i++){
				gets(map[i]);
				for (int j = 0; j < w; j++){
					if (map[i][j] == 'S' ||map[i][j]=='A'){
						vex[vexnum].h = i;
						vex[vexnum].w = j;
						vex[vexnum].step = 0;
						vexid[i][j] = vexnum;
						vexnum++;
					}
				}
		}
		//dfs构造图
		for (int i = 0; i < vexnum; i++){
			memset(visit, 0, 110 * 110);
			visit[vex[i].h][vex[i].w] = 1;
			dfs(vex[i],h,w,i);
		}
		//Prim
		prim(vexnum);
	}
	return 0;
}