a_10068.cpp

UVa ACM 10068 Accepted Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;

typedef struct{
	int x;
	int y;
	int C;
	int P;
}Position;

typedef struct{
	char path[120];
	int pathcnt;
}Path;

typedef struct{
	int value;
	int carry;
}Element;

int cnt;
int R,C;
int dirx[4] = { -1, 0,1, 0};
int diry[4] = { 0,-1, 0, 1};
char rev[4] = {'S','E','N','W'};
char Map[20+2][20+2];
int flag[20+2][20+2];
int Mark[20+2][20+2];
char S[20+1];
Position p[12];
int pcnt;
Path path[10+2][10+2];
Element DP[12][1<<12];
int T[12][1<<12];
int W;

void Search(int a){
	memset(flag,0,sizeof(flag));
	memset(DP,0,sizeof(DP));

	int b;
	int i,j,k;
	int x1,y1,x,y,tmpx,tmpy;
	for(i=0;i<22;i++)
		for(j=0;j<22;j++)
			flag[i][j] = -1;


	x1 = p[a].x;
	y1 = p[a].y;
	flag[x1][y1] = 0;
	queue<int> qx;
	queue<int> qy;
	qx.push(x1);
	qy.push(y1);
	while(!qx.empty()){
		x = qx.front();
		y = qy.front();
		qx.pop();
		qy.pop();
		for(i=0;i<4;i++){
			tmpx = x+dirx[i];
			tmpy = y+diry[i];
			if(tmpx>=1&&tmpx<=R&&tmpy>=1&&tmpy<=C){
				if(Map[tmpx][tmpy] == '.' && flag[tmpx][tmpy] == -1){
					flag[tmpx][tmpy] = flag[x][y]+1;
					qx.push(tmpx);
					qy.push(tmpy);
				}
				if((Map[tmpx][tmpy] == '*' || Map[tmpx][tmpy] == 'S' || Map[tmpx][tmpy] == 'T')&& flag[tmpx][tmpy] == -1){
					flag[tmpx][tmpy] = flag[x][y]+1;
					b = Mark[tmpx][tmpy];
					path[a][b].pathcnt = flag[tmpx][tmpy];
					path[a][b].path[path[a][b].pathcnt] = 0;
					qx.push(tmpx);
					qy.push(tmpy);


					while(flag[tmpx][tmpy] !=0){
						for(k=0;k<4;k++)
							if(flag[tmpx+dirx[k]][tmpy+diry[k]] == flag[tmpx][tmpy]-1){
								path[a][b].path[flag[tmpx][tmpy]-1] = rev[k];
								tmpx += dirx[k];
								tmpy += diry[k];
								break;
							}
					}
				}
			}
		}
	}
}
int bitcount(int x){
	int i=0;
	int cnt = 0;
	if((x & 1) == 1)
		cnt++;
	for(i=1;i<12;i++){
		x >>=1;
		if((x & 1) == 1)
			cnt++;
	}
	return cnt;
}

void TSP(){
	int i,j,k,t;
	for(i=1;i<=pcnt;i++){
		DP[i][0].carry = p[i].C+W;
		if(path[0][i].pathcnt !=0)
			DP[i][0].value = path[0][i].pathcnt*W + p[i].P;
	}
	DP[1+pcnt][0].carry = W;
	DP[1+pcnt][0].value = path[0][pcnt+1].pathcnt*W;

	int totat,min,buf,buf2,ttmp;
	for(i=1;i<=pcnt-1;i++){
		totat = 1<<pcnt;
		for(j=1;j<totat;j++)
			if(bitcount(j) == i){
				for(k=1;k<=pcnt;k++)
					if((j & (1<<(k-1)))==0){
						min = 1e8;
						for(t=1;t<=pcnt;t++){
							if((j & (1<<(t-1))) != 0){
								int tmp = j & (((1<<pcnt)-1) ^ (1<<(t-1)));
								buf2 = DP[t][tmp].carry + p[k].C;
								if(DP[t][tmp].value != 0 && path[k][t].pathcnt!=0){
									buf = path[k][t].pathcnt*DP[t][tmp].carry + p[k].P + DP[t][tmp].value;
									if(buf < min){
										min = buf;
										ttmp = t;
									}
								}
							}
						}
						if(min < 1e8){
							DP[k][j].value = min;
							DP[k][j].carry =buf2;
							T[k][j] = ttmp;
						}
					}
			}
	}

	if(pcnt != 0){
		j = (1<<pcnt)-1;
		k= pcnt+1;
		min = 1e8;
		for(t=1;t<=pcnt;t++){
			if((j & (1<<(t-1))) !=0){
				int tmp = j & (((1<<pcnt)-1) ^ (1<<(t-1)));
				buf2 = DP[t][tmp].carry;
				if(DP[t][tmp].value != 0 && path[k][t].pathcnt!=0){
					buf = path[k][t].pathcnt*DP[t][tmp].carry + DP[t][tmp].value;
					if(buf < min){
						min = buf;
						ttmp = t;
					}
				}
			}
		}
		DP[k][j].value = min;
		DP[k][j].carry =buf2;
		T[k][j] = ttmp;
	}
	else{
		k=1;
		j=0;
	}

	int record[12];
	printf("Hunt #%d\n",++cnt);
	if(DP[k][j].value  >= 1e8 || DP[k][j].value == 0)
		printf("The hunt is impossible.\n");
	else{
		printf("Minimum energy required = %d cal\n",DP[k][j].value);
		record[0]=0;
		record[pcnt+1] = pcnt+1;
		while(T[k][j] != 0){
			record[bitcount(j)] = T[k][j];
			k = T[k][j];
			j = j & (((1<<pcnt)-1) ^ (1<<(k-1)));
		}
		for(i=0;i<pcnt;i++){
			printf("%sP",path[record[i]][record[i+1]].path);
		}
		printf("%s\n",path[record[pcnt]][pcnt+1].path);
	}
	printf("\n");
}

int main(){
	cnt = 0;
	int i,j;
	int tmpr,tmpc;
	while(scanf("%d %d",&R,&C)!=EOF && !(R==0&&C==0)){
		memset(Mark,0,sizeof(Mark));
		memset(path,0,sizeof(path));
		memset(DP,0,sizeof(DP));
		memset(T,0,sizeof(T));
		pcnt = 0;
		for(i=1;i<=R;i++){
			scanf("%s",S);
			for(j=1;j<=C;j++){
				Map[i][j] = S[j-1];
				if(Map[i][j] == 'S'){
					p[0].x = i;
					p[0].y = j;
					Mark[i][j] = 0;
				}
				if(Map[i][j] == '*'){
					p[++pcnt].x = i;
					p[pcnt].y = j;
					Mark[i][j] = pcnt;
				}
				if(Map[i][j] == 'T'){
					tmpr = i;
					tmpc = j;
				}
			}
		}
		p[pcnt+1].x = tmpr;
		p[pcnt+1].y = tmpc;
		Mark[tmpr][tmpc] = pcnt+1;
		scanf("%d",&W);
		for(i=1;i<=pcnt;i++)
			scanf("%d %d",&p[i].P,&p[i].C);

		for(i=0;i<=pcnt+1;i++)
			Search(i);
		TSP();
	}
	return 0;
}