a_10231.cpp

UVa ACM 10231 Accepted Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<bitset>
#include<stack.h>

using namespace std;

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

typedef struct{
	Pos pos;
	int SecCnt;
}Path;

char Map[30][31];
int Flag[30][30];
bool Tag[30][30];
int ST[11][11];	//Self to Treasure
int GT[11][11];	//Guard Machines to Treasure
int treasurecnt;
Pos T_Pos[10];
Pos Start;
int M,N;
int counter;

void S_BFS(Pos S){
	int i,j,k;
	bool IsDone;
	static int dirx[4];
	static int diry[4];

	dirx[0] =  0; dirx[1] = 1; dirx[2] = 0; dirx[3] = -1;
	diry[0] = -1; diry[1] = 0; diry[2] = 1; diry[3] =  0;

	for(i=0;i<treasurecnt;i++){
		/*initialize*/
		IsDone = false;
		for(j=0;j<30;j++){
			memset(&Flag[j][0],0,sizeof(int)*30);
			memset( &Tag[j][0],false,sizeof(bool)*30);
		}

		/*BFS*/
		queue<Path> q;
		Path path;
		int a,b,c;

		path.pos = S;
		path.SecCnt = 0;
		q.push(path);

		Flag[S.row][S.col] = 0;
		Tag[S.row][S.col] = true;
		Flag[T_Pos[i].row][T_Pos[i].col] = -1;
		Tag[T_Pos[i].row][T_Pos[i].col] = true;

		while(!q.empty()){

			Path tmp;
			tmp = q.front();
			c = tmp.SecCnt + 1;
			q.pop();

			for(k=0;k<4;k++){
				a = tmp.pos.row + diry[k];
				b = tmp.pos.col + dirx[k];
				if( a>=0 &&  b>=0 && a<M && b<N ){
					if(Flag[a][b] == 0 && Tag[a][b] == false && Map[a][b] != '#'){
						Path buf;
						buf.pos.row = a;
						buf.pos.col = b;
						buf.SecCnt = c;
						Flag[a][b] = c;
						q.push(buf);
					}
					else if(Flag[a][b] == -1 && Tag[a][b] == true){
						ST[0][i+1] = c;
						ST[i+1][0] = c;
						IsDone = true;
						break;
					}
				}
			}
			if(IsDone)
				break;

		}
	}
}

void G_BFS(Pos G){
	int i,j,k;
	bool IsDone;
	static int dirx[4];
	static int diry[4];

	dirx[0] = -1; dirx[1] = 0; dirx[2] = 1; dirx[3] =  0;
	diry[0] =  0; diry[1] = 1; diry[2] = 0; diry[3] = -1;

	for(i=0;i<treasurecnt;i++){
		/*initialize*/
		IsDone = false;
		for(j=0;j<30;j++){
			memset(&Flag[j][0],0,sizeof(int)*30);
			memset( &Tag[j][0],false,sizeof(bool)*30);
		}

		/*BFS*/
		queue<Path> q;
		Path path;
		int a,b,c;

		path.pos = G;
		path.SecCnt = 0;
		q.push(path);

		Flag[G.row][G.col] = 0;
		Tag[G.row][G.col] = true;
		Flag[T_Pos[i].row][T_Pos[i].col] = -1;
		Tag[T_Pos[i].row][T_Pos[i].col] = true;

		while(!q.empty()){

			Path tmp;
			tmp = q.front();
			c = tmp.SecCnt + 1;
			q.pop();

			for(k=0;k<4;k++){
				a = tmp.pos.row + diry[k];
				b = tmp.pos.col + dirx[k];
				if( a>=0 &&  b>=0 && a<M && b<N ){
					if(Flag[a][b] == 0 && Tag[a][b] == false && Map[a][b] != '#'){
						Path buf;
						buf.pos.row = a;
						buf.pos.col = b;
						buf.SecCnt = c;
						Flag[a][b] = c;
						q.push(buf);
					}
					else if(Flag[a][b] == -1 && Tag[a][b] == true){
						if(c < GT[0][i+1]){
							GT[0][i+1] = c;
							GT[i+1][0] = c;
						}
						IsDone = true;
						break;
					}

				}
			}
			if(IsDone)
				break;

		}
	}
}

void T_BFS(int No){
	int i,j,k;
	bool IsDone;
	static int dirx[4];
	static int diry[4];

	dirx[0] =  0; dirx[1] = 1; dirx[2] = 0; dirx[3] = -1;
	diry[0] = -1; diry[1] = 0; diry[2] = 1; diry[3] =  0;

	for(i=No+1;i<treasurecnt;i++){
		/*initialize*/
		IsDone = false;
		for(j=0;j<30;j++){
			memset(&Flag[j][0],0,sizeof(int)*30);
			memset( &Tag[j][0],false,sizeof(bool)*30);
		}

		/*BFS*/
		queue<Path> q;
		Path path;
		int a,b,c;

		path.pos = T_Pos[No];
		path.SecCnt = 0;
		q.push(path);

		Flag[T_Pos[No].row][T_Pos[No].col] = 0;
		Tag[T_Pos[No].row][T_Pos[No].col] = true;
		Flag[T_Pos[i].row][T_Pos[i].col] = -1;
		Tag[T_Pos[i].row][T_Pos[i].col] = true;

		while(!q.empty()){

			Path tmp;
			tmp = q.front();
			c = tmp.SecCnt + 1;
			q.pop();

			for(k=0;k<4;k++){
				a = tmp.pos.row + diry[k];
				b = tmp.pos.col + dirx[k];
				if( a>=0 &&  b>=0 && a<M && b<N ){
					if(Flag[a][b] == 0 && Tag[a][b] == false && Map[a][b] != '#'){
						Path buf;
						buf.pos.row = a;
						buf.pos.col = b;
						buf.SecCnt = c;
						Flag[a][b] = c;
						q.push(buf);
					}
					else if(Flag[a][b] == -1 && Tag[a][b] == true){
						ST[No+1][i+1] = c;
						ST[i+1][No+1] = c;
						GT[No+1][i+1] = c;
						GT[i+1][No+1] = c;
						IsDone = true;
						break;
					}
				}
			}
			if(IsDone)
				break;

		}
	}
}

int D[12][4098];

void TSP_Module(){
	int i,j,k;
	int min,buf;
	unsigned int NumAllSet;
	unsigned int TmpSetNum;
	unsigned int A;
	bitset<32> Set;
	bitset<32> TmpSet;
	int Max = 0;
	int Time = 1000000000;


	NumAllSet = (unsigned int)(pow((double)2,treasurecnt));

	for(i=0;i<=treasurecnt;i++)
		for(j=0;j<NumAllSet;j++)
			D[i][j] = 1000000000;

	for(i=1;i<=treasurecnt;i++)
		if(ST[0][i]+1 < GT[0][i]){
			D[i][0] = ST[0][i]+1;
			if(Time > D[i][0])
				Time = D[i][0];
			Max = 1;
		}

	for(k=1;k<=treasurecnt;k++)	// loop 1
		for(A=1;A<NumAllSet;A++){	// loop 2
			Set = A;
			if(Set.count() == k){
				for(i=1;i<=treasurecnt;i++){	// loop 3
					if(!Set.test(i-1)){
						min = 1000000000;
						for(j=1;j<=treasurecnt;j++){	// loop 4
							if(Set.test(j-1)){
								TmpSet = A;
								TmpSet.flip(j-1);
								TmpSetNum = TmpSet.to_ulong();
								buf = ST[i][j] + 1 + D[j][TmpSetNum];
								if(buf >= GT[0][i])
									buf = 1000000000;
								if(buf < min)
									min = buf;
							}
						}
						D[i][A] = min;
						if(D[i][A] != 1000000000 && (k+1) >= Max){
							if((k+1) == Max && D[i][A] < Time)
								Time = D[i][A];
							else if((k+1) > Max){
								Max = k+1;
								Time = D[i][A];
							}
						}
					}
				}
			}
		}

	printf("Case %d:\n",++counter);
	if(Max == 0)
		printf("No treasures can be collected.\n\n");
	else{
		printf("Maximum number of collectible treasures: %d.\n",Max);
		printf("Minimum Time: %d sec.\n\n",Time);
	}

}

int main(){

	Pos tmp;
	counter = 0;
	while(scanf("%d %d",&M,&N)!=EOF){
		int i,j;
		treasurecnt = 0;

		/*initialize*/
		for(i=0;i<30;i++)
			memset(&Map[i][0],0,sizeof(char)*31);

		for(i=0;i<11;i++)
			for(j=0;j<11;j++){
				ST[i][j] = 1000000000;
				GT[i][j] = 1000000000;
			}

		/*input*/
		for(i=0;i<M;i++)
			scanf("%s",&Map[i][0]);

		/*set treasure position*/
		for(i=0;i<M;i++)
			for(j=0;j<N;j++)
				if(Map[i][j] == '*'){
					T_Pos[treasurecnt].row = i;
					T_Pos[treasurecnt].col = j;
					treasurecnt++;
				}


		for(i=0;i<M;i++)
			for(j=0;j<N;j++){
				if(Map[i][j] == 'O'){
					tmp.row = i;
					tmp.col = j;
					Start = tmp;
					S_BFS(tmp);
				}
				else if(Map[i][j] == 'X'){
					tmp.row = i;
					tmp.col = j;
					G_BFS(tmp);
				}
			}

		for(i=0;i<treasurecnt;i++)
			T_BFS(i);

		/*#Debug Tag*/
		/*
		for(i=0;i<=treasurecnt;i++){
			for(j=0;j<=treasurecnt;j++){
				printf("%12d ",ST[i][j]);
			}
			printf("\n");
		}
		printf("--------------------------------------------------------------------------------------------------------------------\n");
		for(i=0;i<=treasurecnt;i++){
			for(j=0;j<=treasurecnt;j++){
				printf("%12d ",GT[i][j]);
			}
			printf("\n");
		}
		 */
		TSP_Module();
	}

	return 0;
}