熊猫烧香问题

《熊猫烧香问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Project3:AttackofPandaTimeLimit:3secondsThecomputersinournetworkwereconnectedinanarrayofMrowsandNcolumns.Anyonecomputerwasconnecteddirectlytoonlythecomputershorizontallyorverticallyadjacenttoit.Atthebeginning,TcomputerswereinfectedwiththePandavirus,eachwi

2、thadifferentvariation,denotedbyType1,Type2,...TypeT.GiventhateachcomputerinthenetworkhadaspecificintegerdefenselevelL(0

3、ctedcomputerstothecleanones;lIfacomputerhadalreadybeeninfectedbyonevariationofthevirus,itwouldneverbeinfectedagainbyanothervariation;lTheattackingcapabilityofthePandaviruswouldincreaseeachday.Inday1,theviruscouldonlyinfectcomputerswiththedefenselevel1prov

4、idedthattheviruscouldreachthosecomputers.AcomputerwithadefenselevelL>1couldstopthevirus.IndayD,theviruscouldspreadtoallthecomputersconnectedwiththeirdefenselevelL£D,providedthattheviruswasnotstoppedbyanycomputerwithadefenselevelL>D;lWithinthesameday,theTy

5、pe1variationwouldattackfirstandinfectallthecomputersitcouldreach.ThenthevirusvariationsType2,Type3,...TypeTwouldbeactivatedinorder.Giventhenetworkinthefollowingfigureasanexample:Inthe3´4network,therewereinitiallytwocomputersinfectedbyvariationsofType1andT

6、ype2,respectively.Wemayrepresentthestatusofthenetworkbya3´4matrix,with–LrepresentingacleancomputerwithdefenselevelL,andapositiveintegerirepresentingthevariationtypeindexbywhichthecomputerwasinfected.Hencethegivennetworkcorrespondstothematrix.Inthefirstday

7、,Type1wasstoppedbyitstwoneighboringcomputers,whileType2attackedthetwocomputersinthe3rdrowwithdefenselevel1.Thematrixthenbecomes.Inthesecondday,Type1attackedallthecleancomputerswithdefenselevels1and2,whileType2hadnothingtodosincetheonlycleancomputeritcould

8、reachhadadefenselevel3.Thematrixnowbecomes.Finallyinthethirdday,Type1attackedalltherestofthecleancomputersandchangedthematrixinto.Yourtaskistocalculatethenumberofcomputersthatwereinfectedbysomespecificvirusvariation