算法竞赛入门经典习题第6章

_onlinejudge&Itemid=8&category=839&page=show_problem&problem=747

1/3

SpatialStructures

Computergraphics,imageprocessing,andGIS(geographicinformationsystems)allmakeuseofadatastructurecalledaquadtree.Quadtreesrepresentregionalorblockdataefficientlyandsupportefficientalgorithmsforoperationsliketheunionandintersectionofimages.

Aquadtreeforablackandwhiteimageisconstructedbysuccessivelydividingtheimageintofourequalquadrants.Ifallthepixelsinaquadrantarethesamecolor(allblackorallwhite)thedivisionprocessforthatquadrantstops.Quadrantsthatcontainbothblackandwhitepixelsaresubdividedintofourequalquadrantsandthisprocesscontinuesuntileachsubquadrantconsistsofeitherallblackorallwhitepixels.Itisentirelypossiblethatsomesubquadrantsconsistofasinglepixel.

Forexample,using0forwhiteand1forblack,theregionontheleftbelowisrepresentedbythematrixofzerosandonesinthemiddle.Thematrixisdividedintosubquadrantsasshownontherightwheregraysquaresrepresentsubquadrantsthatconsistentirelyofblackpixels.

Aquadtreeisconstructedfromtheblockstructureofanimage.Therootofthetreerepresentstheentirearrayofpixels.Eachnon-leafnodeofaquadtreehasfourchildren,correspondingtothefoursubquadrantsoftheregionrepresentedbythenode.Leafnodesrepresentregionsthatconsistofpixelsofthesamecolorandthusarenotsubdivided.Forexample,theimageshownabove,withtheblockstructureontheright,isrepresentedbythequadtreebelow.

Leafnodesarewhiteiftheycorrespondtoablockofallwhitepixels,andblackiftheycorrespondtoablockofallblackpixels.Inthetree,eachleafnodeisnumberedcorrespondingtotheblockitrepresentsinthediagramabove.Thebranchesofanon-leafnodeareorderedfromleft-to-rightasshownforthenorthwest,northeast,southwest,andsoutheastquadrants(orupper-left,upper-right,lower-left,lower-right).

Atreecanberepresentedbyasequenceofnumbersrepresentingtheroot-to-leafpathsofblacknodes.Eachpathisabasefivenumberconstructedbylabelingbrancheswith1,2,3,or4withNW=1,NE=2,SW=3,SE=4,andwiththeleastsignificantdigitofthebasefivenumbercorrespondingtothebranchfromtheroot.Forexample,thenodelabeled4has

pathNE,SWwhichis325(base5)or1710(base10);thenodelabeled12haspathSW,SEor435=2310;andthenodelabeled15haspathSE,SW,NWor1345=4410.Theentiretreeisrepresentedbythesequenceofnumbers(inbase10)

9141722234463698894113

Writeaprogramthatconvertsimagesintoroot-to-leafpathsandconvertsroot-to-leafpathsintoimages.

Input

Theinputcontainsoneormoreimages.Eachimageissquare,andthedataforanimagestartswithanintegern,where|n|isthelengthofasideofthesquare(alwaysapoweroftwo,with|n|≤64)followedbyarepresentationoftheimage.Arepresentationiseitherasequenceofn2zerosandonescomprisedof|n|linesof|n|digitsperline,orthesequenceofnumbersthatrepresenttheroot-to-leafpathsofeachblacknodeinthequadtreethatrepresentstheimage.

Ifnispositive,thezero/onerepresentationfollows;ifnisnegative,thesequenceofblacknodepathnumbers(inbase10)follows.Thesequenceisterminatedbythenumber-1.Aone-nodetreethatrepresentsl-blackimageisrepresentedbythenumber0.Aone-nodetreethatrepresentsl-whiteimageisrepresentedbyanemptysequence(nonumbers).

ofdataissignaledbyavalueof0forn.

Output

Foreachimageintheinput,firstoutputthenumberoftheimage,asshowninthesampleoutput.Thenoutputthealternateformoftheimage.

Iftheimageisrepresentedbyzerosandones,theoutputconsistsofroot-to-leafpathsofallblacknodesinthequadtreethatrepresentstheimage.Thevaluesshouldbebase10representationsofthebase5pathnumbers,andthevaluesshouldbeprintedinsortedorder.Iftherearemorethan12blacknodes,printanewlineafterevery12nodes.Thetotalnumberofblacknodesshouldbeprintedafterthepathnumbers.

Iftheimageisrepresentedbytheroot-to-leafpathsofblacknodes,theoutputconsistsofanASCIIrepresentationoftheimagewiththecharacter`.'usedforwhite/zeroandthecharacter`*'usedforblack/one.Thereshouldbencharactersperlineforann×nimage.

Printablanklineb