3007982_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

int x, y;
char map[51][51];
int id[51][51], ID;
struct Edge
{
	int v1;
	int v2;
	int weight;
};

int e;
Edge E[10000];
int visited[51][51];

bool valid(int a,int b)
{
	if(a<0||b<0||a>=x||b>=y||map[a][b]=='#'||visited[a][b]!=-1)
		return 0;
	return 1;
}

void bfs(int i,int j)
{
	int k;
	int mov[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
	typedef pair <int,int> type;
	queue <type> que;
	int x, y;
	
	type t;
	memset(visited,-1,sizeof(visited));
	visited[i][j] = 0;
	t.first = i;
	t.second = j;
	que.push(t);
	while(!que.empty())
	{
		t = que.front();
		x = t.first;
		y = t.second;
		que.pop();
		for(k = 0; k < 4; k++)
		{
			int a = x+mov[k][0];
			int b = y+mov[k][1];
			
			if(valid(a,b))
			{
				visited[a][b] = visited[x][y]+1;
				que.push(make_pair(a,b));
				if(map[a][b]=='A'||map[a][b]=='S')
				{
					E[e].v1 = id[i][j];
					E[e].v2 = id[a][b];
					E[e].weight = visited[a][b];
					e++;
				}
			}
		}
	}
}

void kruskal(int n)
{
	int i, k, j;
	int m1, m2, sn1, sn2;
	int vest[200];

	for(i = 0; i < n; i++)
		vest[i] = i;
	k = 1;
	j = 0;
	int MSW = 0;
	while(k < n)
	{
		m1 = E[j].v1; m2 = E[j].v2;
		sn1 = vest[m1]; sn2 = vest[m2];
		if(sn1!=sn2)
		{
			k++;
			MSW += E[j].weight;
			for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("%d\n",MSW);
}

bool cmp(Edge a,Edge b)
{
	return a.weight < b.weight;
}

int main()
{
	int cas, i, j;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&x,&y);
		x += y;
		y = x - y;
		x = x - y;
		getchar();
		for(i = 0; i < x; i++)
		{
			gets(map[i]);
		}
		memset(id,-1,sizeof(id));
		ID = 0;
		for(i = 0; i < x; i++)
		{
			for(j = 0; j < y; j++)
			{
				if(map[i][j]=='A'||map[i][j]=='S')
				{
					id[i][j] = ID++;
				}
			}
		}
		e = 0;
		for(i = 0; i < x; i++)
		{
			for(j = 0; j < y; j++)
			{
				if(id[i][j]!=-1)
				{
					bfs(i,j);
				}
			}
		}
		sort(E,E+e,cmp);
		kruskal(ID);
	}
	return 0;
}