首页 > 搜索 > BFS搜索 > HDU 4543-三足鼎立-排序-[解题报告]HOJ
2015
07-25

HDU 4543-三足鼎立-排序-[解题报告]HOJ

三足鼎立

问题描述 :

  “纷纷世事无穷尽,天数茫茫不可逃。鼎足三分已成梦,后人凭吊空牢骚。”

  三国的各种传奇故事被千百年传诵,为人们津津乐道。魏、蜀、吴三个势力相互制约,同时也相互利用,“三”的神奇和精妙尽在其中。于是,这个问题也是关于“三”的。

  在一个N * M的地图上,两个点(x1, y1)和(x2, y2)之间的距离被定义成曼哈顿距离,魏、蜀、吴三个势力要在这个地图上分别选择自己的据点。由于地图上某些点已经被其他势力占据,为了避免不必要的冲突,他们希望自己的据点与其他被占据的点都可以保持一定的距离,包括他们三个势力据点的相互距离,也要满足约束。

  现在,三个势力不可思议的开了一次首脑峰会,商谈据点的安排问题。你,作为一个像鲁肃大师一样爱好和平的外交家,要给出最大的限制距离,使得至少有一种安排方案满足条件。

输入:

输入第一行为T,表示有T组测试数据。
每组数据以两个整数N和M开始,表示地图的规模。接下来的N行,每一行包含一个长度为M的字符串,表示地图,‘.’表示空地,’F’表示这里已被其他势力占据。地图至少有三个空格以供选择。

[Technical Specification]
1. 1 <= T <= 74
2. 1 <= N, M <= 74

输出:

输入第一行为T,表示有T组测试数据。
每组数据以两个整数N和M开始,表示地图的规模。接下来的N行,每一行包含一个长度为M的字符串,表示地图,‘.’表示空地,’F’表示这里已被其他势力占据。地图至少有三个空格以供选择。

[Technical Specification]
1. 1 <= T <= 74
2. 1 <= N, M <= 74

样例输入:

2
4 4
F...
....
....
....
4 4
F..F
....
....
F..F

样例输出:

Case 1: 3
Case 2: 1

Hint
第一组样例中,他们可以约定依次选择 (1, 4), (4, 1), (4, 4) 作为据点,这样两两之间的距离都为3,到 (1, 1) 的最小距离也是3,是一种最优的选择。

这道题感觉很坑。。不过,注意一些小问题。

参考http://www.cnblogs.com/Lattexiaoyu/archive/2013/03/31/2992553.html改进了原来自己的复杂度。

当无被占领时,其实枚举边缘也可以。但有计算公式,直接用了。

当有占领时,BFS出每个空的格到被占领的最小距离,然后枚举求出最小的D。

1)起先自己也是如上面的做,但做法不够优美T了。BFS时,起初是把占领的和未占的分开存枚举计算。其实这样复杂度就很高了。直接按一般的BFS就可以了,因为先到达空格的必定是距离短的,所以,复杂度变成了o(NM)。

2)枚举求D也有小技巧。直接三重循环必须T。可以改为枚举D,三重循环判断D是否符合要求,符合则D++,不符合即能得到答案了。

为什么不符合就能得到答案?因为排序后的点当枚举到q时,剩下的三重循环会把所有情况都列举到,所以不符合D-1就是解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m;

struct Node{
	int x,y,dis;
	Node(){}
	Node(int xx,int yy,int d){x=xx,y=yy,dis=d;}
}que[10300],dic[5300];
int cd,head,tail;
char s[100];
int dir[4][2]={
	{0,1},
	{0,-1},
	{1,0},
	{-1,0}
};


int cal(int i,int j,int x,int y){
	return abs(i-x)+abs(j-y);
}

int map[80][80];

int uslove(){/*
	int ans=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<m;k++){
				int t=min(cal(0,i,j,m-1),cal(j,m-1,n-1,k));
				ans=max(ans,min(cal(0,i,n-1,k),t));
			}
			for(int k=0;k<n;k++){
				int t=min(cal(0,i,j,m-1),cal(j,m-1,k,0));
				ans=max(ans,min(cal(0,i,k,0),t));
			}
		}
	}
//	printf("%d\n",ans);*/
//	return ans;
	 if(n == 1) return m / 3;
	 if(m == 1) return n / 3; 
     return (2*n + 2*m - 4)/3;
}

bool cmp(Node a,Node b){
	if(a.dis<b.dis) return true;
	return false;
}

bool check(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]==0) return true;
	return false;
}

void BFS(){
/*	for(int i=0;i<cd;i++){
		dic[i].dis=200;
		for(int j=0;j<co;j++){
			dic[i].dis=min(dic[i].dis,cal(dic[i].x,dic[i].y,occ[j].x,occ[j].y));
	//		cout<<dis[i]<<endl;
		}
	}*/
	Node p,tmp;
	while(head<tail){
		p=que[head++];
		for(int i=0;i<4;i++){
			tmp.x=p.x+dir[i][0];
			tmp.y=p.y+dir[i][1];
			if(check(tmp.x,tmp.y)){
				tmp.dis=p.dis+1;
				map[tmp.x][tmp.y]=tmp.dis;
				dic[cd++]=Node(tmp.x,tmp.y,p.dis);
				que[tail++]=tmp;
			}
		}
	}
}

void slove(){
	/*
	int ans=-1;
	int t;
	for(int i=0;i<cd;i++){
		if(dis[i]<ans) continue;
		for(int j=i+1;j<cd;j++){
			t=min(dis[j],dis[i]);
			if(t<ans) continue;
			for(int k=j+1;k<cd;k++){
				int t1=min(dis[k],t);
				if(t1<ans) continue;
				t1=min(t1,cal(dic[i].x,dic[i].y,dic[j].x,dic[j].y));
				t1=min(t1,cal(dic[i].x,dic[i].y,dic[k].x,dic[k].y));
				t1=min(t1,cal(dic[j].x,dic[j].y,dic[k].x,dic[k].y));
				ans=max(t1,ans);
			}
		}
	}
	printf("%d\n",ans);*/
	sort(dic,dic+cd,cmp);
	int q=0,d=1;
	while(q<cd){
		bool flag=false;
		for(int i=q;i<cd;i++){
			for(int j=i+1;j<cd;j++){
				if(cal(dic[i].x,dic[i].y,dic[j].x,dic[j].y)<d) continue;
				for(int k=j+1;k<cd;k++){
					if(cal(dic[i].x,dic[i].y,dic[k].x,dic[k].y)>=d&&cal(dic[k].x,dic[k].y,dic[j].x,dic[j].y)>=d){
						flag=true;
						break;
					}
				}
				if(flag) break;
			}
			if(flag) break;
		}
		if(!flag) break;
		d++;
		while(q<cd&&dic[q].dis<d)
		q++;
	}
	printf("%d\n",d-1);
}

int main(){
	int T,icase=0;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		cd=0; int cc=0;
		head=tail=0;
		memset(map,0,sizeof(map));
		for(int i=0;i<n;i++){
			scanf("%s",s);
			for(int j=0;j<m;j++){
				if(s[j]=='F'){
					map[i][j]=1;
					que[tail++]=Node(i,j,1);
				}
				else cc++;
			}
		}
		printf("Case %d: ",++icase);
		if(cd==n*m){
			printf("%d\n",uslove());
		}
		else{
			BFS();
			slove();
		}
	}
	return 0;
}

  

参考:http://www.cnblogs.com/jie-dcai/p/4421590.html