poj-3026 -Borg Maze -bfs+prim(MST)

http://poj.org/problem?id=3026 
タイトルは1つの最も外で#に囲まれた図を与えて、SがすべてのA点に着くことを求めて、必要とする歩数.
注意Sは分身することができて、Aは最大で100個あって、それではSは100点に分けることができて、実はSもAと見なすことができて、図の中で
あるAはつながっている最小生成ツリーで、bfsで彼らの間の辺権値を求めてprimを走ります.
OKです...データが小さい.暴力的なアルゴリズムで
trickがnで、mの後ろにスペースがある可能性があります.getcharを落とす必要があります.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
double min(double a,double b)
{ 	return a>b?b:a;}
double max(double a,double b)
{ 	return a<b?b:a;}
int inf=2147483647;
double eps=0.000001;   
int mp[55][55];
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node
{
	int x,y;node(){}
	node(int a,int b){x=a;y=b;}
	node(int a,int b,int c){x=a;y=b;w=c;}
	int w;
};  
struct edge
{
	int x,y,v;
	edge(){}
	edge(int a,int b,int c)
	{x=a,y=b,v=c;}
};edge tm[105*105]; 
int cmp(edge a,edge b)
{
	return a.v<b.v;
}  
int who[55][55];					// A  
node que[1000005];					//  A     1		
int vis[105][105];					//   bfs         
int cost[105][105];					//     
void bfs(int xx,int yy,int num)		//   
{
	memset(vis,0,sizeof(vis));
	queue<node> q;int i;
	q.push(node(xx,yy,0));
	int flag=0;
	vis[xx][yy]=1;
	while(!q.empty())
	{
		node tp=q.front();q.pop(); 
	 	for (i=0;i<4;i++)
		{
			int x=tp.x+dx[i];int y=tp.y+dy[i]; 
			if (vis[x][y]||mp[x][y]=='#') continue;
			if (who[x][y])	
			{
				cost[num][who[x][y]]=tp.w+1; 
				flag=tp.w+1;
			}
			q.push(node(x,y,tp.w+1));
			vis[x][y]=1;
		}
	} 

}
int dis[105];
int main()

{ 


	
	int  i,j,k;  
	int t;cin>>t;
	while(t--)
	{ 
		int ok=0;
		int que_ok=0; 
		cin>>m>>n;
		char c=getchar();
		while(c!='
') c=getchar();
	memset(cost,0,sizeof(cost));
	memset(who,0,sizeof(who));
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=m;j++)
			{
				scanf("%c",&mp[i][j]);
				if (mp[i][j]=='S')
				{mp[i][j]='A';} 
				
				if (mp[i][j]=='A')
				{que[++que_ok]=node(i,j);who[i][j]=que_ok;}
			}
			getchar();
		}
		 
		for (i=1;i<=que_ok;i++) 
			bfs(que[i].x,que[i].y,i);  

		dis[1]=0;
		int ans=0; 
		for (i=2;i<=que_ok;i++)
		{
			if (cost[1][i])
				dis[i]=cost[1][i];
			else
				dis[i]=inf;
		}
		
		for (i=1;i<que_ok;i++)
		{
			int minn=inf;
			int mini=0;
			for (j=1;j<=que_ok;j++)
			{
				 
				if (dis[j]<minn&&dis[j]!=0)
				{
					minn=dis[j];mini=j;
				}
			}
			dis[mini]=0;
			ans+=minn;
			for(j=1;j<=que_ok;j++)
			{
				if (dis[j]&&cost[mini][j])
					if (cost[mini][j]<dis[j])
						dis[j]=cost[mini][j];
			}
		}
		printf("%d
",ans);
	}
	
	
	
	return 0;
}