#include<iostream>
#include<queue>
#define  INF 100000
using namespace std;
struct st {
	int i;
	int j;
}stu[150],a,d;
char str[100][100],ch;
int n,m,length;
int c[150][150];
int step;
queue<st> q;
void dfs(st b){
	step = 0;
	int e[150][150],i,j;
	for(i = 0;i<n;i++)
		for(j = 0;j<m;j++)
			e[i][j] = 0;
	while (1) {
		int len = q.size();
		while(len>0){
			a = q.front();
			if(a.i == b.i&&a.j==b.j)
				return ;
			if(a.i-1>=0&&str[a.i-1][a.j]!='#'&&e[a.i-1][a.j]==0){
				d.i = a.i -1;
				d.j = a.j;
				q.push(d);
				e[d.i][d.j] = 1;
			}
			if(a.i+1<n&&str[a.i+1][a.j]!='#'&&e[a.i+1][a.j]==0){
				d.i = a.i+1;
				d.j = a.j;
				q.push(d);
				e[d.i][d.j] = 1;
			}
			if(a.j+1<m&&str[a.i][a.j+1]!='#'&&e[a.i][a.j+1]==0){
				d.i = a.i;
				d.j = a.j+1;
				q.push(d);
				e[d.i][d.j] = 1;
			}
			if(a.j-1>=0&&str[a.i][a.j-1]!='#'&&e[a.i][a.j-1]==0){
				d.i = a.i;
				d.j = a.j-1;
				q.push(d);
				e[d.i][d.j] = 1;
			}
			len--;
			q.pop();

		}
		step++;
	}
 }
void prim(){
	int lowcost[150];
	int closet[150];
	bool s[150];
	s[0] = true;
	int i,j,k;
	for(i = 1;i<length;i++){
		lowcost[i] = c[0][i];
		closet[i] = 1;
		s[i] = false;
	}

	for(i = 0;i<n;i++){
		int min = INF;
		j = 0;
		for(k = 1;k<length;k++)
			if(lowcost[k]<min&&(!s[k])){
				min = lowcost[k];
				j = k;
			}
		s[j] = true;
		for(k = 1;k<length;k++)
			if(c[j][k]<lowcost[k]&&(!s[k])){
				lowcost[k] = c[j][k];
				closet[k]=j;
			}
	}
	int sum = 0;
	for(i = 1;i<length;i++)
		sum+=lowcost[i];
	printf("%d\n",sum);


}
int main()
{
	int t,i,j;
//	freopen("in.txt","r",stdin);
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d",&m,&n);
		length = 0;
		for(i = 0;i<n;i++){
			scanf("%c",&ch);
			for(j = 0;j<m;j++){
				scanf("%c",&str[i][j]);
				if(str[i][j]=='S'||str[i][j]=='A'){
					stu[length].i = i;
					stu[length].j = j;
					length++;
				}
			}
		}
		for(i = 0;i<length;i++){
			c[i][i] = 0;
			for(j = i+ 1;j<length;j++){
				q.push(stu[i]);
				dfs(stu[j]);
				c[i][j] = step;
				c[j][i] = step;
				step = 0;
			while (!q.empty()) 
				q.pop();
			}
		}
		prim();
	}
	return 0;
}

• Re:牛啊！救救小第，怎么会超时啊！应该怎样优化 (2455) 467814865 2008-07-26 12:29:58