a_10818.cpp

UVa ACM 10818 Accepted Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#define size 12

using namespace std;

typedef struct{
	int r;
	int c;
}Position;

typedef struct{
	char path[256];
	int cnt;
}PATH;

char Map[20+2][20+2];
int flag[20+2][20+2];
int Record[20+2][20+2];
int W[size+1][size+1];
PATH path[size+1][size+1];
Position p[size+1];
int pcnt;
int r,c;

int dirr[4] = {0,-1,1,0};
int dirc[4] = {1,0,0,-1};
char rev[4] = {'W','S','N','E'};
int DP[size+1][1<<size];
int RD[size+1][1<<size];

void BFS(int x){
	int i,j;
	int tmpr,tmpc,bufr,bufc;
	for(i=0;i<=21;i++)
		for(j=0;j<=21;j++)
			Record[i][j] = -1;
	tmpr = p[x].r;
	tmpc = p[x].c;
	Record[tmpr][tmpc] = 0;
	queue<int> qr;
	queue<int> qc;
	qr.push(tmpr);
	qc.push(tmpc);
	while(!qr.empty()){
		tmpr = qr.front();
		tmpc = qc.front();
		qr.pop();
		qc.pop();
		for(i=0;i<4;i++){
			bufr = tmpr+dirr[i];
			bufc = tmpc+dirc[i];
			if(bufr>=1&&bufr<=r&&bufc>=1&&bufc<=c){
				if(Map[bufr][bufc]==' ' && Record[bufr][bufc] == -1){
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
					qr.push(bufr);
					qc.push(bufc);
				}
				if((Map[bufr][bufc] == '*' || Map[bufr][bufc] == 'S')&& Record[bufr][bufc] == -1){
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
					//printf("%d\n",Record[bufr][bufc]);
					qr.push(bufr);
					qc.push(bufc);
					W[x][flag[bufr][bufc]]= Record[bufr][bufc];
					path[x][flag[bufr][bufc]].cnt = Record[bufr][bufc];
					path[x][flag[bufr][bufc]].path[Record[bufr][bufc]] = 0;
					int y = flag[bufr][bufc];
					int tmprr,tmpcc,bufrr,bufcc;
					queue<int> qqr;
					queue<int> qqc;
					qqr.push(bufr);
					qqc.push(bufc);
					while(!qqr.empty()){
						tmprr = qqr.front();
						tmpcc = qqc.front();
						qqr.pop();
						qqc.pop();
						for(int i=0;i<4;i++){
							bufrr = tmprr + dirr[i];
							bufcc = tmpcc + dirc[i];
							if(bufrr>=1&&bufrr<=r&&bufcc>=1&&bufcc<=c){
								if(Record[bufrr][bufcc] >=0 && Record[bufrr][bufcc] == Record[tmprr][tmpcc]-1){
									path[x][y].path[Record[bufrr][bufcc]] = rev[i];
									//printf("%d %c\n",Record[bufrr][bufcc],rev[i]);
									qqr.push(bufrr);
									qqc.push(bufcc);
									break;
								}
							}
						}
					}

				}


			}
		}
	}
}

void lookup(){
	int i,j;
	int tmpr,tmpc,bufr,bufc;
	for(i=0;i<=21;i++)
		for(j=0;j<=21;j++)
			Record[i][j] = -1;
	tmpr = p[0].r;
	tmpc = p[0].c;
	Record[tmpr][tmpc] = 0;
	queue<int> qr;
	queue<int> qc;
	qr.push(tmpr);
	qc.push(tmpc);
	while(!qr.empty()){
		tmpr = qr.front();
		tmpc = qc.front();
		qr.pop();
		qc.pop();
		for(i=0;i<4;i++){
			bufr = tmpr+dirr[i];
			bufc = tmpc+dirc[i];
			if(bufr>=1&&bufr<=r&&bufc>=1&&bufc<=c){
				if(Map[bufr][bufc]==' ' && Record[bufr][bufc] == -1){
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
					qr.push(bufr);
					qc.push(bufc);
				}
				if(Map[bufr][bufc] == '*' && Record[bufr][bufc] == -1){
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
					pcnt++;
					flag[bufr][bufc] = pcnt;
					p[pcnt].r = bufr;
					p[pcnt].c = bufc;
					qr.push(bufr);
					qc.push(bufc);
				}
			}
		}
	}
}

int bitcount(int x){
	int cnt=0;
	if((x & 1) == 1)
		cnt++;
	for(int i=0;i<=10;i++){
		x >>=1;
		if((x & 1) == 1)
			cnt++;
	}
	return cnt;
}

void TSP(){
	int PP[20];
	memset(DP,0x7f,sizeof(DP));
	memset(RD,0x7f,sizeof(RD));
	int i,j,k,s,t,total,min,buf,tmp;
	PATH tmppath;
	total = 1<<pcnt;
	for(i=1;i<=pcnt;i++){
		DP[i][0] = W[i][0];
		RD[i][0] = 0;
	}
	for(k=1;k<=pcnt;k++)
		for(s=1;s<total;s++)
			if(bitcount(s) == k){
				for(i=1;i<=pcnt;i++)
					if((s&(1<<(i-1))) == 0){
						min = 100000000;
						memset(tmppath.path,0x7f,sizeof(tmppath.path));
						tmppath.path[255] = 0;
						for(j=1;j<=pcnt;j++)
							if((s&(1<<(j-1))) != 0){
								tmp = s & ( ((1<<pcnt)-1) ^ (1<<(j-1)) );
								if(DP[j][tmp] < 100000000){
									buf = W[i][j] + DP[j][tmp];
									/*-------------------------------*/
									int tempa,tempb,cc;
									char Str[256];
									Str[0] = 0;
									PP[k+1] = i;
									PP[k] = j;
									PP[0] = 0;
									tempa = j;
									tempb = ( s ^ (1<<(tempa-1)) );
									for(cc=k-1;cc>=1;cc--){
										PP[cc] = RD[tempa][tempb];
										tempa = PP[cc];
										tempb = (tempb ^ (1<<(tempa-1)));
									}
									for(cc=1;cc<=k+1;cc++)
										strcat(Str,path[PP[cc-1]][PP[cc]].path);
									/*-------------------------------*/
									if(buf < min || (buf == min && strcmp(tmppath.path,Str) == 1)){
										strcpy(tmppath.path,Str);
										tmppath.cnt = strlen(tmppath.path);
										min = buf;
										t = j;
									}
								}
							}
						if(min < 100000000){
							DP[i][s] = min;
							RD[i][s] = t;
						}
					}
			}
	min = 100000000;
	memset(tmppath.path,0x7f,sizeof(tmppath.path));
	tmppath.path[255] = 0;
	for(i=1;i<=pcnt;i++){
		tmp = ( ((1<<pcnt)-1) ^ (1<<(i-1)) );
		buf = W[0][i]+DP[i][tmp];
		/*-------------------------------*/
		int tempa,tempb,cc;
		char Str[256];
		Str[0] = 0;
		PP[pcnt+1] = 0;
		PP[pcnt] = i;
		PP[0] = 0;
		tempa = i;
		tempb = ( ((1<<pcnt)-1) ^ (1<<(tempa-1)) );
		for(cc=pcnt-1;cc>=1;cc--){
			PP[cc] = RD[tempa][tempb];
			tempa = PP[cc];
			tempb = (tempb ^ (1<<(tempa-1)));
		}
		for(cc=1;cc<=pcnt+1;cc++)
			strcat(Str,path[PP[cc-1]][PP[cc]].path);
		/*-------------------------------*/
		if(buf < min  || (buf == min && strcmp(tmppath.path,Str) == 1)){
			strcpy(tmppath.path,Str);
			tmppath.cnt = strlen(tmppath.path);
			min = buf;
			t = i;
		}
	}

	PP[pcnt+1] = 0;
	PP[pcnt] = t;
	PP[0] = 0;
	buf = t;
	tmp = ( ((1<<pcnt)-1) ^ (1<<(buf-1)) );
	for(i=pcnt-1;i>=1;i--){
		PP[i] = RD[buf][tmp];
		buf = PP[i];
		tmp = (tmp ^ (1<<(buf-1)));
	}
	for(i=1;i<=pcnt+1;i++)
		printf("%s",path[PP[i-1]][PP[i]].path);
	printf("\n");

}
int main(){
	int i,j,len;
	char S[20+2];
	while(scanf("%d %d",&r,&c)!=EOF && !(r==0&&c==0)){
		getchar();
		memset(Map,0,sizeof(Map));
		memset(flag,0,sizeof(flag));
		memset(W,0x7f,sizeof(W));
		memset(path,0,sizeof(path));
		pcnt = 0;
		for(i=1;i<=r;i++){
			gets(S);
			len = strlen(S);
			if(len != c){
				S[c] = 0;
				for(j=len;j<c;j++)
					S[j] = ' ';
			}
			for(j=1;j<=c;j++){
				Map[i][j] = S[j-1];
				if(Map[i][j] == 'S'){
					p[0].r = i;
					p[0].c = j;
				}
				if(Map[i][j] == 'X')
					Map[i][j] = '#';
			}
		}

		lookup();

		for(i=0;i<=pcnt;i++)
			BFS(i);

		if(pcnt == 0)
			printf("Stay home!\n");
		else
			TSP();
	}
	return 0;
}