3033194_tle.cc

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

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

int w, h, n;
char map[21][21];
int dis[11][11];

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

int bfs(int x,int y,int a,int b)
{
	int visited[21][21];
	typedef pair <int,int> type;
	typedef pair <type,int> Type;
	Type p;
	p.first.first = x;
	p.first.second = y;
	p.second = 0;
	memset(visited,0,sizeof(visited));
	visited[x][y] = 1;
	queue <Type> 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.first.first;
		ty = p.first.second;
		w = p.second;
		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;
				//if(map[wx][wy]=='.')
				{
					que.push(make_pair(make_pair(wx,wy),w+1));
				}
				if(wx==a&&wy==b)
				{
					return w+1;
				}
			}
		}
	}
	return 0;
}

void calc()
{
	int i;
	int a[12], ans;

	a[0] = 0;
	ans = 2100000000;
	for(i = 1; i < n; i++)
	{
		a[i] = i;
	}
	do
	{
		int tmp = 0;
		for(i = 0; i < n-1; i++)
		{
			tmp += dis[a[i]][a[i+1]];
			if(dis[a[i]][a[i+1]]==0)
			{
				tmp = 2100000000;
				break;
			}
		}
		if(tmp < ans)
		{
			ans = tmp;
		}
	}while(next_permutation(&a[1],&a[1]+n-1));
	printf("%d\n",ans);
}

int marked[12];

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;
	
	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;
}