3033210_ac_124ms_624k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <queue>
#include <algorithm>
#define INF 2100000000

using namespace std;

int w, h, n;
char map[21][21];
int dis[12][12];
int f[12][2049];
int a[17];
struct Node 
{
	int no;
	int id;
	int mark[16];
	int pos[16];
}num[2049];

int valid(int a,int b)
{
	if(a<0||b<0||a>=w||b>=h||map[a][b]=='x')
		return 0;
	return 1;
}

struct node
{
	int aa, bb, cc;
};

int bfs(int x,int y,int a,int b)
{
	int visited[21][21];

	node p, pp;
	p.aa = x;
	p.bb = y;
	p.cc = 0;
	memset(visited,0,sizeof(visited));
	visited[x][y] = 1;
	queue <node> que;

	que.push(p);
	int tx, ty;
	int wx, wy, w;
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

	while(!que.empty())
	{
		p = que.front();
		tx = p.aa;
		ty = p.bb;
		w = p.cc;
		que.pop();
		for(int i = 0; i < 4; i++)
		{
			wx = tx+mov[i][0];
			wy = ty+mov[i][1];
			if(valid(wx,wy)&&!visited[wx][wy])
			{
				visited[wx][wy] = 1;
				pp.aa = wx;pp.bb = wy;
				pp.cc = w+1;
				que.push(pp);
				if(wx==a&&wy==b)
				{
					return w+1;
				}
			}
		}
	}
	return 0;
}

bool cmp(Node c,Node b)
{
	if (c.no!=b.no)
		return c.no<b.no;
	else
		return c.id<b.id;
}

void init()
{
	int i, k;

	a[1] = 1;
	for (i = 2; i < 16; i++)
	{
		a[i] = a[i-1]*2;
	}
	for (k = 1; k < 2048; k++)
	{
		num[k].id = k;
		num[k].no = 0;
		memset(num[k].mark,0,sizeof(num[k].mark));
		for (i = 1; k >= a[i]; i++)
		{
			if (k&a[i])
			{
				num[k].pos[num[k].no++] = i;
				num[k].mark[i] = 1;
			}
		}	
	}
	sort(&num[1],&num[1]+2047,cmp);
}


void calc()
{
	int i, j, mark, N;
	int p, k, min;

	mark = 1;
	n--;
	N = 1<<n;
	memset(f,0,sizeof(f));
	for (i = 1; mark; i++)
	{
		if (num[i].no==1)
			continue;
		if (num[i].no==n&&num[i].id==N-1)
			mark = 0;
		if (num[i].id>=N)
		{
			continue;
		}
		for (j = 1; j <= n; j++)
		{
			if (num[i].mark[j]==0)
				continue;
			p = 0;
			for (k = 0; k < num[i].no; k++)
			{
				if (num[i].pos[k]!=j)
					p |= a[num[i].pos[k]];
			}
			min = INF;
			if (num[i].no==1)
			{
				min = 0;
			} 
			else
			{
				for (k = 0; k < num[i].no; k++)
				{
					if (num[i].pos[k]!=j)
					{
						if (f[num[i].pos[k]][p]+dis[num[i].pos[k]][j]<min)
						{
							min = f[num[i].pos[k]][p]+dis[num[i].pos[k]][j];
						}
					}
				}
			}
			f[j][num[i].id] = min;
		}
	}
	min = INF;
	for (i = 1; i <= n; i++)
	{
		if (min>f[i][N-1]+dis[0][i])
		{
			min = f[i][N-1]+dis[0][i];
		}
	}
	printf("%d\n",min);
}

int marked[16];

void dfs(int v)
{
	int i;

	marked[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(dis[v][i]&&!marked[i])
		{		
			dfs(i);
		}
	}
}

bool connected()
{
	int i;

	memset(marked,0,sizeof(marked));
	dfs(0);
	for(i = 0; i < n; i++)
	{
		if(!marked[i])
		{
			return false;
		}
	}
	return true;
}

void createGraph()
{
	int i, j;
	int pos[11][2];

	n = 1;
	for(i = 0; i < w; i++)
	{
		for(j = 0; j < h; j++)
		{
			if(map[i][j]=='*')
			{
				pos[n][0] = i;
				pos[n][1] = j;
				n++;
			}
			if(map[i][j]=='o')
			{
				pos[0][0] = i;
				pos[0][1] = j;
			}
		}
	}
	memset(dis,0,sizeof(dis));
	for(i = 0; i < n; i++)
	{
		for(j = i+1; j < n; j++)
		{
			dis[i][j] = dis[j][i] = bfs(pos[i][0],pos[i][1],pos[j][0],pos[j][1]);
		}
	}
	if(!connected())
	{
		puts("-1");
	}
	else
	{
		calc();
	}
}

int main()
{
	int i;
	
	init();
	while(scanf("%d%d",&h,&w)==2)
	{
		if(w==0&&h==0)
		{
			break;
		}
		for(i = 0; i < w; i++)
		{
			scanf("%s",map[i]);
		}
		createGraph();
	}
	return 0;
}