資源描述:
《熊貓燒香問題》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
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