2226.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2226 on 2006-05-14 at 22:12:31 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int DM = 10;
const int SM = 1 << DM;
const int WM = 24, HM = 24;
const int INF = 1 << 20;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

char map[HM][WM];
int w, h, bn, dis[DM][DM+1];

inline bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w && map[x][y] != 'x'; }
bool go(int, int);

int main()
{
	int i, j, k, best[SM][DM];
	
	while(scanf("%d %d\n", &w, &h) != EOF && w != 0) {
		int block[DM+1]; bn = 0;
		for(i = 0; i < h; i++) {
			gets(map[i]);
			for(j = 0; j < w; j++)
				if(map[i][j] == 'o') map[i][j] = DM;
				else if(map[i][j] == '*') { map[i][j] = bn; block[bn++] = i * w + j; }
		}
		bool can = true;
		for(i = 0; i < bn; i++) 
			can &= go(block[i]/w, block[i]%w);
		if(!can) { printf("-1\n"); continue; }
		int ms = 1<<bn; best[0][0] = 0;
		for(i = 0; i < ms; i++)
			for(j = 0; j < bn; j++) {
				if(!(i & (1<<j))) continue;
				else if(i == (1<<j)) { best[i][j] = dis[j][DM]; continue; }
				int st = i ^ (1<<j); best[i][j] = INF;
				for(k = 0; k < bn; k++)
					if(st & (1<<k)) best[i][j] = min(best[i][j], best[st][k]+dis[k][j]);
			}
		int md = INF;
		for(i = 0; i < bn; i++) md = min(md, best[ms-1][i]);
		printf("%d\n", md);
	}
	
	return 0;
}

bool go(int bx, int by)
{
	int step[HM][WM], o = map[bx][by], vn = 0, i;
	memset(step, -1, sizeof(step));
	step[bx][by] = 0; dis[o][o] = 0;
	queue<pii> Q; Q.push(pii(bx, by));
	while(!Q.empty()) {
		pii p = Q.front(); Q.pop();
		int x = p.first, y = p.second;
		for(i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy) || step[cx][cy] != -1) continue;
			step[cx][cy] = step[x][y]+1; Q.push(pii(cx, cy));
			if(map[cx][cy] <= DM) { dis[o][map[cx][cy]] = step[cx][cy]; vn++; }
		}
	}
	return vn == bn;
}