3026.cpp

pku 3026 北大ACM网站上的算法题

// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std;

#define MAXWH 50
#define MAXAN 100
#define SMARK 0
#define WALLMARK 111
#define SPACMARK 112

int N;//50
int W,H;//50
char pcMap[MAXWH+1][MAXWH+1];
unsigned char pDis[MAXAN+1][MAXAN+1];
int nANum;//aliens数目
struct POINT
{
	int x,y;
	POINT(int _x,int _y)
	{set(_x,_y);}
	POINT(){}
	void set(int _x,int _y)
	{x=_x;y=_y;}
	POINT operator+(const POINT& pt)
	{
		return POINT(x+pt.x,y+pt.y);
	}
};
POINT ptList[MAXAN+1];
POINT dir[]={POINT(1,0),POINT(0,1),POINT(-1,0),POINT(0,-1)};

POINT Q[(MAXWH-1)*(MAXWH-1)];
int tail,front;

void bfs(int nIdxSeed,int nLeftAliNum)
{
	if(!nLeftAliNum)
		return;
	POINT ptSeed=ptList[nIdxSeed];
	short flag[MAXWH+1][MAXWH+1]={0};

	tail=front=0;
	Q[tail++]=ptSeed;

	pcMap[ptSeed.y][ptSeed.x]=SPACMARK;//后续搜索不用再处理该点
	flag[ptSeed.y][ptSeed.x]=1;
	while (front!=tail)
	{
		POINT ptCur=Q[front++];
		for (int i=0;i<4;i++)
		{
			POINT ptNex=ptCur+dir[i];
			if (flag[ptNex.y][ptNex.x]||pcMap[ptNex.y][ptNex.x]==WALLMARK)
				continue;
			flag[ptNex.y][ptNex.x]=flag[ptCur.y][ptCur.x]+1;
			if (pcMap[ptNex.y][ptNex.x]<=nANum)
			{//是Alien或S
				pDis[nIdxSeed][pcMap[ptNex.y][ptNex.x]]=
					pDis[pcMap[ptNex.y][ptNex.x]][nIdxSeed]=
					flag[ptNex.y][ptNex.x]-1;
				nLeftAliNum--;
				if (!nLeftAliNum)
					return;
			}
			Q[tail++]=ptNex;
		}
	}
}
char closet[MAXAN+1];
int pMinCost[MAXAN+1];
int InitPrim()
{
	int nMinCost=99999,nMinIdx=-1;
	
	memset(closet,0,sizeof(closet));
	memset(pMinCost,0,sizeof(pMinCost));
	for (int i=1;i<=nANum;i++)
	{
		pMinCost[i]=pDis[0][i];
		if (pMinCost[i]<nMinCost)
		{
			nMinCost=pMinCost[i];
			nMinIdx=i;
		}
	}
	closet[0]=1;
	closet[nMinIdx]=1;
	return nMinIdx;
}
int Refresh(int nCurIdx)
{
	int nNexIdx=-1,nMinCost=99999;
	for (int i=1;i<=nANum;i++)
	{
		if (closet[i])
			continue;
		if(pMinCost[i]>pDis[nCurIdx][i])
			pMinCost[i]=pDis[nCurIdx][i];
		if(pMinCost[i]<nMinCost)
		{
			nMinCost=pMinCost[i];
			nNexIdx=i;
		}
	}
	return nNexIdx;
}
int prime()
{
	int nCurIdx=InitPrim();
	int nCostSum=pMinCost[nCurIdx];
	for (int i=0;i<nANum;i++)
	{
		nCurIdx=Refresh(nCurIdx);
		closet[nCurIdx]=1;
		nCostSum+=pMinCost[nCurIdx];
	}
	return nCostSum;
}
void Solve()
{
	for (int i=0;i<nANum;i++)
	{//共nANum+1个结点
		bfs(i,nANum-i);
	}
	printf("%d\n",prime());
}
void Init()
{
	nANum=0;
	scanf("%d%d",&W,&H);
	while (getchar()!='\n')
		continue;
	for (int y=0;y<H;y++)
	{
		gets(pcMap[y]);
		for (int x=0;x<W;x++)
		{
			switch(pcMap[y][x])
			{
			case 'S'://0
				ptList[0].set(x,y);
				pcMap[y][x]=SMARK;
				break;
			case 'A'://1～100
				ptList[++nANum].set(x,y);
				pcMap[y][x]=nANum;
				break;
			case '#':
				pcMap[y][x]=WALLMARK;
				break;
			case ' ':
				pcMap[y][x]=SPACMARK;
				break;
			}
		}
	}
}
int main(int argc, char* argv[])
{
	scanf("%d",&N);
	for (int i=0;i<N;i++)
	{
		Init();
		Solve();
	}
	return 0;
}

// 6 5              
// ######
// #A#A##
// # # A#
// #S  ##
// ######