解题报告程序购房计划

1、CTSC2002 - Day1 - Problem2购房计划（House）问题描述Bill 和Scott 是商业对手。他们都计划在 Javaville 城市一幢房子，但是他们希望自己的住宅尽量远离对方的住宅。由于 Javaville 是一座新兴的城市，所以暂时还没有地图，于是，他们只能从当地人的口中搜集信息，这些信息包括建筑物的位置和建筑物之间的距离。尽管这些信息并不完整，但是它们都是正确的。Javaville 的街道是一个矩形网格，包含 m 条东西的街道，依次用大写字母 A,B,C,标识，n 条南北的街道，依次用数字 0,1,2,标识。把两条街道的交点称为交叉路口，两个交叉路口之间的一段街道

2、称为街区。所有的建筑物都位于交叉路口处，每个交叉路口至多只有一座建筑物。建筑物之间的距离定义为从一座建筑物到另一座建筑物所需经过的最少的街区数。例如，Bill 和Scott 搜集了以下这些信息：城市中有 5 条东西的街道和 5 条南北的街道；住宅 1 位于交叉路口 A0；邮局位于交叉路口 A4；学校与住宅 1 距离 4 个街区；住宅 2 与邮局距离 6 个街区；学校与邮局距离 6 个街区；住宅 3 与邮局距离 6 个街区；图 1：h1,h2,h3 = 住宅,p = 邮局s = 学校根据以上信息，可以得到Javaville 城市可能的两种布局。发现：住宅 1，邮局和学校的位置都已经确定了，而住宅

3、 2 可以位于 C0 或E2，住宅 3 可以位于 C0 或 E2。于是，城市中总是存在两座住宅相距 6 个街区（地图 1 中的h1 与h3，地图 2 中的h1 与h2）。但是，对于确定的两座住宅，可以保证的最长距离只有 4 个街区 (h2 与h3 的距离总是 4 个街区)。于是，要告诉 Bill和 Scott，尽管总是存在两座相距 6 个街区的住宅，然而最安全的建议是：一人住宅 2，另一人住宅 3。下面给出所求数值的严格定义：一个可行的城市布局 S 的直径 d(S)定义为该布局中距离最远的两座住宅之间的距离。对于确定的两座住宅i, j，它们的安全系数ei, j定义为在所有可行的城市布局中，住宅

4、i, j 之间的距离的最小值。Bill 和Scott 希望你编写一个程序，根据他们所搜集到的信息，计算出 D 和E。其中：D =mind(S) ；E =maxei, j。同时你还要给出最安全的购房建议，即所有满足ei, j=E 的住宅i, j。对于上面的例子，第一种布局的 d(S1)=6，第二种布局的 d(S2)=6。每两座住宅之间的安全系数是：e1,2=2，e1,3=2，e2,3=4。于是：D= mind(S1),d(S2)=6，E= maxe1,2,e1,3,e2,3=4，最安全的购房建议是：住宅 2 与住宅 3。输入文件house.in 第一行包含两个正整数m, n（1=m, n=10）

5、，分别表示东西的街道数目和南北的街道数目。第二行包含一个整数，表示所搜集到的信息条数 t(1=t=50)。文件从第三行开始每行描述一条所搜集到的信息，每条信息都是以下两种形式之一：nameLOCATIONrc或者nameDISTANCEdname2这两种形式分别描述建筑物的位置和建筑物之间的距离。其中，name 和 name2 是仅包含数字和小写字母的字符串，长度不超过 20，表示建筑的名称。r 是 A 到 J 之间的大写字母，c 是一个数字，表示建筑物所位于的交叉路口。d 是一个正整数，表示两座建筑物之间的距离。如果建筑物名称的前五个字符是小写字母“house”，那么表示这是一座可以的住宅，

6、否则表示一座非民用的建筑物。如果信息是第二种形式，那么其中的name2 一定面的信息中出现过。这组信息中至少包含两座可以的住宅，至多包含 25 座不同的建筑物。输出文件 house.out 的第一行包含两个整数，分别表示 D 和 E，之间用一个空格隔开。输出文件从第二行开始给出所有的最安全的购房建议，每个购房建议占一行，购房建议可以以任意的顺序排列，但是不能重复。输出文件每行末尾不得有多余的空格。输出文件输入文件问题分析这道题目的最好方法，也只能在搜索里打转，似乎没有比搜索更好的算法了。所以说，问题转换为怎样优化搜索过程。首先搜索的框架可以确定如下：将可以确定位置的建筑先安置好，剩下的每个建筑

7、，根据条件列出他所可能放置的位置，然后选择一个建筑，穷举它所有可能位置，再对其他建筑进行安置 对所有的状态，依次每两栋住宅的最短距离，以及最远的两幢住宅。也就是最后要求输出的两个值。这无疑是一个阶乘式的复杂度，因此，不得不采取优化措施。不难发现，当确定了一个建筑以后，剩余建筑的可能位置会大大减少。因此，不难证明，每次穷举的时候，选择一个可能放置位置最少的建筑，再进行穷举，效率会高许多。如果住宅已经穷举完毕，下几座建筑（非住宅）没有安放，这时候穷举这些建筑的所有位置是耗时而无效的。因为，如果这些建筑存在一种以上的布置优化 2优化 1house.out6 4house2 house3house.i

8、n5 56house1 LOCATION A 0 toffice LOCATION A 4school DISTANCE 4 house1 house2 DISTANCE 6toffice school DISTANCE 6toffice house3 DISTANCE 6toffice 输入输出样例方案，那么显然所有方案中，住宅的位置都一定，那么就不影响到所需求解的数据。因此，如果找到了一个方案之后，递归过程就应该回溯到最后一幢住宅的位置开始搜索，而不是前一座建筑。不难发现，优化 1 中忽略了放置位置数相同时的择优方案。然而，有了优化 2，这个择优方案就展现在眼前。如果住宅的放置位置数与其他

9、建筑相同，那么住宅优先选取。程序程序中将 N*M 的地图，从 1.N*M，方便 Hash 操作。(*$APPTYPE Console*) Program House;Uses SysUtils; ConstInf OufMaxNM MaxBuildings= House.in;= House.out;= 10;= 25;TypeTBuildings建筑信息= Array 1.MaxBuildings Of Record建筑名称Name: String;建筑被安放位置,0表Place,示有待安放可放置位置的数NumPut :eger;目程序算法设计优化 3CanPut : Array 1.Max

10、NM*MaxNM Ofeger;可放置位置，0 表示可放Dis存放读入的与其它建筑距离的信息End;: Array 1.MaxBuildings Ofeger;TDistance= Array 1.MaxNM*MaxNM,1.MaxNM*MaxNM Ofeger;任意两个位置的距离任意位置TNumber= Array 1.MaxNM,1.MaxNM Ofeger;对应的一维TSafe= Array 1.MaxBuildings,1.MaxBuildings Ofeger;存放任意两栋建筑之间可能的最短距离TBelongHouse= Array 1.MaxBuildings Of;BelongH

11、ousei，建筑i 是否为住宅Var平面图大小，w表示建筑n,m,w:eger;数目Buildings Distance Number BelongHouse Time1: TBuildings;: TDistance;: TNumber;: TBelongHouse;: Extended;Procedure Init; VarFin i,j,k,l,t Str: Text; eger;: String;:返回 Str 的建筑，如Function Find(Str:String):eger;果第一次出现则Vari Begin:eger;For i:=1 to w DoIf Buildingsi

12、.Name=Str Then Begin Find:=i;Exit; End;Inc(w); Find:=w;Buildingsw.Name:=Str;End; BeginAssign(Fin,Inf); Reset(Fin);Fillchar(Buildings,Sizeof(Buildings),0);Readln(Fin,n,m); w:=0;Readln(F);给平面图For i:=1 to n DoFor j:=1 to m Do Numberi,j:=(i-1)*m+j;For i:=1 to n DoFor j:=1 to m DoFor k:=1 to n DoFor l:=1

13、 to m Do计算任意两点距离DistanceNumberi,j,Numberk,l:=abs(i-k)+abs(j-l);For i:=1 to t Do BeginReadln(Fin,Str); j:=Find(Copy(Str,1,( ,Str)-1);Delete(Str,1,( ,Str); 安 放 建 If Copy(Str,1,8)=LOCATION Then Begin筑Delete(Str,1,9); k:=ord(Str1)-ord(A)+1; Delete(Str,1,2); l:=ord(Str1)-ord(0)+1;Buildingsj.Place:=Number

14、k,l; End设置两个建筑的距离Else BeginDelete(Str,1,9);Val(Copy(Str,1, Delete(Str,1, l:=Find(Str);( ,Str)-1),k,k); ( ,Str);Buildingsj.Disl:=k;Buildingsl.Disj:=k;End;End;For i:=1 to w Do Buildingsi.NumPut:=n*m;Close(Fin);End;Procedure Put(i:将建筑 i 放置在 Buildingsi.Placeeger);位置上将其它建筑因此无法放置的位置置为Varij,k Begin:eger;Fo

15、r j:=1 to w Do BeginIf Buildingsi.Disj0 Then For k:=1 to N*M DoIf (Buildingsj.CanPutk=0) And距离不满足条件(DistanceBuildingsi.Place,kBuildingsi.Disj)ThenBeginBuildingsj.CanPutk:=i; Dec(Buildingsj.NumPut);End;If Buildingsj.CanPutBuildingsi.Place=0 Then Begin 该位置被第 i个建筑占用Buildingsj.CanPutBuildingsi.Place:=i;

16、 Dec(Buildingsj.NumPut);End;End;End;Procedure UnPut(i: 取 消 建 筑i放 置 在eger);Buildingsi.Place 位置将其它建筑在 Put 中置为 i 的全部恢Var复j,k Begin:eger;For j:=1 to w Do BeginIf Buildingsi.Disj0 Then For k:=1 to N*M Do距离不满足的If Buildingsj.CanPutk=i Then Begin Buildingsj.CanPutk:=0; Inc(Buildingsj.NumPut);End;If Building

17、sj.CanPutBuildingsi.Place=i Then Begin 该位置被第i个建筑占用Buildingsj.CanPutBuildingsi.Place:=0; Inc(Buildingsj.NumPut);End;End;End;Procedure FindHouse;Vari Begin生成BelongHouse 数组:eger;For i:=1 to w DoIf Copy(Buildingsi.Name,1,5)=house Then BelongHousei:=TrueElse BelongHousei:=False;End; Procedure VarFou i,j,

18、Longest, MaxSafet;: Text;存放每种可能布局直径的最小值:eger;存放任意两栋建筑之间可: TSafe;能的最短距离优化 2，到退回最近一座Back:;住宅时用尝试安置第o 个建筑Procedure Tryit(o:Vari,j,Max Begineger);:eger;产生了一种布局If o=w+1 Then Begin地图直径f BelongHousei Thenf BelongHousej Then任意两座房子Max:=0;For i:=1 to w-1For j:=i+1 to wBeginIf DistanceBuildingsi.Place,Building

19、sj.PlaceMaxThenMax:=DistanceBuildingsi.Place,Buildingsj.Place;If DistanceBuildingsi.Place,Buildingsj.PlaceSafei,j ThenSafei,j:=DistanceBuildingsi.Place,Buildingsj.Place; 更新它们的 Safe 属性以及End;Max更新直径的最小If MaxLongest Then Longest:=Max;值Back:=True; Exit;End;找到一个可放置位置数最小的建i:=0;筑iFor j:=1 to w DoIf (Buildi

20、ngsj.Place=0) And (i=0) Or(Buildingsj.NumPutBuildingsi.NumPut) Or(Buildingsj.NumPut=Buildingsi.NumPut) And BelongHousej)Then Begini:=j;If Buildingsi.NumPut=1 Then Break;End;穷举所放置的位置For j:=1 to n*m DoIf Buildingsi.CanPutj=0 Then Begin Buildingsi.Place:=j;Put(i);放入j下一层递归Tryit(o+1);取消放入UnPut(i);Buildin

21、gsi.Place:=0;如果已经到If BelongHousei Then Back:=False;一幢住宅如果还没到住宅，接If Back Then Exit;着End;End; BeginAssign(Fou,Ouf); Rewrite(Fou);Longest:=high(Longest); Fillchar(Safe,Sizeof(Safe),$7F);j:=0;For i:=1 to w Do给定位置的建筑预先放置If Buildingsi.Place0 Then Begin Put(i);Inc(j); End;Back:=False; Tryit(j+1);Max:=0;For i:=1 to w-1 DoIf BelongHousei Then For j:=i+1 to w DoIf BelongHousej Then求出问题所求的EIf Safei,jMax Then Max:=S