a_10944.cpp

UVa ACM 10944 Accepted Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<bitset>
#define MAX(a,b) (a>b?a:b)

using namespace std;

int N;
int W[16][16];
int D[16][32768];
int MinLength;

void TSP(){
	int i,j,k;
	int min,buf,index;
	unsigned int NumAllSet;
	unsigned int A;
	bitset<32> Set;
	bitset<32> TmpSet;
	unsigned int TmpSetNum;

	NumAllSet = (double)(pow((double)2,N-1));

	for(i=1;i<N;i++)
		D[i][0] = W[i][0];
	
	for(k=1;k<=N-2;k++)	// loop 1
		for(A=1;A<NumAllSet;A++){	// loop 2
			Set = A;
			if(Set.count() == k){
				for(i=1;i<N;i++){	// loop 3
					if(!Set.test(i-1)){
						min = 1000000000;
						for(j=1;j<N;j++){	// loop 4
							if(Set.test(j-1)){
								TmpSet = A;
								TmpSet.flip(j-1);
								TmpSetNum = TmpSet.to_ulong();
								buf = W[i][j] +D[j][TmpSetNum];//
								if(buf < min)
									min = buf;
							}
						}
						D[i][A] = min;
					}
				}
			}
		}
		min = 1000000000;
		Set = NumAllSet-1;
		for(j=1;j<N;j++){
			if(Set.test(j-1)){
				TmpSet = NumAllSet-1;
				TmpSet.flip(j-1);
				TmpSetNum = TmpSet.to_ulong();
				buf = W[0][j] +D[j][TmpSetNum];
				if(buf < min)
					min = buf;
			}
		}
		D[0][NumAllSet-1] = min;
		MinLength = D[0][NumAllSet-1];
}

typedef struct OriPos{
	int row;
	int col;
};

int main(){
	int m,n;
	int p,q,r;
	char temp[21];
	OriPos City[16];

	while(scanf("%d %d",&m,&n)!=EOF){
		/*Read Input Data*/
		r=1;
		for(p=0;p<m;p++){
			scanf("%s",temp);
			for(q=0;q<n;q++){
				if(temp[q] == '#'){
					City[r].row = p;
					City[r].col = q;
					r++;
				}
				else if(temp[q] == 'L'){
					City[0].row = p;
					City[0].col = q;
				}
			}
		}
		N = r;
		if(N > 1){
			/*Compute W[][]*/
			for(p=0;p<r;p++)
				for(q=0;q<r;q++)
					if(p!=q)
						W[p][q] = MAX(abs(City[p].row-City[q].row),abs(City[p].col-City[q].col));
			/*TSP Process*/
			TSP();
			/*Print Answer*/
			printf("%d\n",MinLength);
		}
		else
			printf("0\n",MinLength);
	}
	return 0;
}