a_10937.cpp

UVa ACM 10944 Accepted Code

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

using namespace std;

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

char Map[50+2][50+2];
int flag[50+2][50+2];
int Record[50+2][50+2];
char Tmp[100+2];
Position Pos[10+1];
int pcnt;	  //N, W, S, E,NW,SE,NE,SW
int dirr[8] = {-1, 0, 1, 0,-1, 1,-1, 1};
int dirc[8] = { 0,-1, 0, 1,-1, 1, 1,-1};
int Cost[10+1][10+1];
int h,w;
int DP[11][1<<10];


void BFS(int Num){
	memset(Record,0,sizeof(Record));
	int i,j,k;
	int tmpr,tmpc;
	int bufr,bufc;

	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++)
			Record[i][j] = -1;

	queue<int> qr,qc;
	qr.push(Pos[Num].r);
	qc.push(Pos[Num].c);
	Record[Pos[Num].r][Pos[Num].c] = 0;

	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<=h && bufc >=1 && bufc <= w && Record[bufr][bufc] == -1){
				if(Map[bufr][bufc] == '.'){
					qr.push(bufr);
					qc.push(bufc);
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
				}
				if(Map[bufr][bufc] == '!'){
					qr.push(bufr);
					qc.push(bufc);
					Record[bufr][bufc] = Record[tmpr][tmpc]+1;
					k = flag[bufr][bufc];
					Cost[Num][k] = Record[bufr][bufc];
					Cost[k][Num] = Record[bufr][bufc];
				}
			}
		}
	}
}

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

void TSP(){
	memset(DP,0x7f,sizeof(DP));
	int i,j,k,t;
	int total;
	int tmp,buf,min;
	total = 1 <<pcnt;
	for(i=1;i<=pcnt;i++)
		DP[i][0] = Cost[0][i];
	for(k=1;k<=pcnt;k++)
		for(t=1;t<total;t++)
			if(bitcount(t) == k){
				for(i=1;i<=pcnt;i++)
					if((t & (1<<(i-1))) == 0){
						min = 100000000;
						for(j=1;j<=pcnt;j++)
							if((t & (1<<(j-1))) != 0 && Cost[i][j] < 100000000){
								tmp = t&(( (1<<(pcnt)) -1) ^ (1<<(j-1)));
								buf = Cost[i][j] + DP[j][tmp];
								if(buf < min)
									min = buf;
							}
						DP[i][t] = min;
					}
			}
	min = 100000000;
	for(i=1;i<=pcnt;i++){
		tmp = (((1<<(pcnt))-1) ^ (1<<(i-1)));
		if(Cost[0][i] < 100000000)
			buf = Cost[0][i] + DP[i][tmp];
		if(buf < min)
			min = buf;
	}
	if(min<100000000)
		printf("%d\n",min);
	else
		printf("-1\n");
}

int main(){
	int i,j,k;
	int tmpr,tmpc;
	bool IsFalse;

	while(scanf("%d %d",&h,&w)!=EOF && !(h==0&&w==0)){
		IsFalse = false;
		memset(Map,0,sizeof(Map));
		memset(flag,0,sizeof(flag));
		memset(Cost,0x7f,sizeof(Cost));
		pcnt = 0;
		for(i=1;i<=h;i++){
			scanf("%s",Tmp);
			for(j=1;j<=w;j++){
				Map[i][j] = Tmp[j-1];
				if(Map[i][j] == '#')
					Map[i][j] = '~';
				if(Map[i][j] == '!'){
					pcnt++;
					Pos[pcnt].r = i;
					Pos[pcnt].c = j;
					flag[i][j] = pcnt;
				}
				if(Map[i][j] == '@'){
					Pos[0].r = i;
					Pos[0].c = j;
					Map[i][j] = '!';
					flag[i][j] = 0;
				}
			}
		}
		for(i=1;i<=h;i++)
			for(j=1;j<=w;j++)
				if(Map[i][j] == '*'){
					for(k=0;k<8;k++){
						tmpr = i+dirr[k];
						tmpc = j+dirc[k];
						if(tmpr>=1&&tmpr<=h&&tmpc>=1&&tmpc<=w)
							if(Map[tmpr][tmpc] == '!' || Map[tmpr][tmpc] == '@'){
								IsFalse = true;
								goto Label;
							}
							else if(Map[tmpr][tmpc] != '*')
								Map[tmpr][tmpc] = '~';
					}

				}
		for(i=1;i<=h;i++)
			for(j=1;j<=w;j++)
				if(Map[i][j] == '*')
					Map[i][j] = '~';


		Label:
		if(!IsFalse){
			if(pcnt != 0){
				for(i=0;i<=pcnt;i++)
					BFS(i);
				TSP();
			}
			else
				printf("0\n");
		}
		else
			printf("-1\n");
	}
	return 0;
}