1857《holecutter》解题报告

《1857《holecutter》解题报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《HoleCutter》解题报告题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1857(No.l857)解法或类型：离散化作者：谢迪题目描述HoleCutterTimeLimit:2000MSMemoryLimit:30000KTotalSubmit:29Accepted:11DescriptionTheassistantsofSummitHeadquartersoftenneedtocutvariousshapesfromthelargesheetofpaper.Forinstanc

2、e,theywanttodistributepostersofvarioussizesetc.Theyhavejustacquiredanewcutterwhichcanmakecutsmuchmorefreelythananyoftheirpreviousmachines,andtheywantyoutowriteaprogramtocalculateexactlywhathappenswhenacomplexseriesofcutsaremade・Inparticular,theyneedtoknowthenumberofholeswhichareforme

3、dinthesheetbythecuts.Thepicturesshowsomeexamplesofsituationsthatcanariseaftercutting.TwoholesTwoholesOneholeOneholeInputTheinputconsistsofseveraloperationdescriptions.EachdescriptionstartswithalinecontaininganintegernumberN,givingthenumberofcutsintheoperation,1<=N<=100.Thislineisfoll

4、owedbyNlinesgivingtheactualcuts.Eachcutwillbegivenbyfourwholenumbersseparatedbyonespace,XI,Yl,X2,Y2,-105

5、aralleltothex・ory-axisofthetable.Theinputwillbeterminatedbyalineconsistingofasingle0,i.e.acuttingoperationdescriptionwithN=0.OutputForeachcuttingoperation,outputasinglelinecontainingthesentence"ThereareHholes.”whereHisthenumberofdistinctholesinthesheetafterallthecutshavebeenmade.Note

6、thattheminimumareaofanyholeis1squareunit.SampleInput61011202231321020113122322012112100SampleOutputThereare2holes.Therearc0holes.SourceCTUOpen2002解题思路本题中所涉及的边的数目最多只有100,而坐标范围却是从・1（）5到105,因此首先対所有的边进行离散化。这样边的坐标范围可以化成0-200o对于某个给出的边的情况（下面分别是题目小给出的图片的前3种）0）格开始用FloodFill,某个格子只能进入与它没有边的格子，每

7、个格子只能到达一次。这样，经过一次FloodFill,剩下的就变成一个个的洞。我们只要再对每个洞进行FloodFill,这一次就不用考虑边的阻隔，只要是未访问过的，且相邻的格子就可以进入。这样就可以统计111需要求的洞的个数。数据结构structTa{intxl,yl,x2,y2;}a[105];〃读入的边structTq{shortx,y;}q[40020];//FloodFill吋宽搜要求用的队列boolCL210J1210JL4],markL210JL210];//分别记录离散化后的边和每个格子是否访问过的标志intx0[210],y0(210];〃离散化

8、记录的坐标时空分析:时间