深度優(yōu)先搜索DFS的應用

深度優(yōu)先搜索DFSZOJProblemSet-1002FireNetTimeLimit:2SecondsMemoryLimit:65536KBSupposethatwehaveasquarecitywithstraightstreets.Amapofacityisasquareboardwithnrowsandncolumns,eachrepresentingastreetorapieceofwall.Ablockhouseisasmallcastlethathasfouropeningsthroughwhichtoshoot.ThefouropeningsarefacingNorth,East,South,andWest,respectively.Therewillbeonemachinegunshootingthrougheachopening.Hereweassumethatabulletissopowerfulthatitcanrunacrossanydistanceanddestroyablockhouseonitsway.Ontheotherhand,awallissostronglybuiltthatcanstopthebullets.Thegoalistoplaceasmanyblockhousesinacityaspossiblesothatnotwocandestroyeachother.Aconfigurationofblockhousesislegalprovidedthatnotwoblockhousesareonthesamehorizontalroworverticalcolumninamapunlessthereisatleastonewallseparatingthem.Inthisproblemwewillconsidersmallsquarecities(atmost4x4)thatcontainwallsthroughwhichbulletscannotrunthrough.Thefollowingimageshowsfivepicturesofthesameboard.Thefirstpictureistheemptyboard,thesecondandthirdpicturesshowlegalconfigurations,andthefourthandfifthpicturesshowillegalconfigurations.Forthisboard,themaximumnumberofblockhousesinalegalconfigurationis5;thesecondpictureshowsonewaytodoit,butthereareseveralotherways.Yourtaskistowriteaprogramthat,givenadescriptionofamap,calculatesthemaximumnumberofblockhousesthatcanbeplacedinthecityinalegalconfiguration.Theinputfilecontainsoneormoremapdescriptions,followedbyalinecontainingthenumber0thatsignalstheendofthefile.Eachmapdescriptionbeginswithalinecontainingapositiveintegernthatisthesizeofthecity;nwillbeatmost4.Thenextnlineseachdescribeonerowofthemap,witha'-'indicatinganopenspaceandanuppercase'X'indicatingawall.Therearenospacesintheinputfile.Foreachtestcase,outputonelinecontainingthemaximumnumberofblockhousesthatcanbeplacedinthecityinalegalconfiguration.Sampleinput:.X..????XX.. 2XX.X3.X.X.X.X.3....XX.XX40Sampleoutput:51524Source:ZhejiangUniversityLocalContest2001Code:#include<cstdio>#include<iostream>usingnamespacestd;#defineMaxlen4charcMap[Maxlen][Maxlen];intiBest,n;boolCanPut(introw,intcol){inti;for(i=row-1;i>=0;i--)〃掃描同一列，因不用掃本身，所以row-1{if(cMap[i][col]=='O')returnfalse;if(cMap[i][col]=='X')break;}for(i=col-1;i>=0;i--) 〃掃描行{if(cMap[row][i]=='O')returnfalse;if(cMap[row][i]=='X')break;}returntrue;}voidsolve(intk,intcurrent)//curretn為放的數目，k為所寫的代號0，1，2，3.。。。n*n{intx,y;if(k==n*n) 〃到達最后一個if(current>iBest){iBest=current;}}else{x=k/n;〃得到x坐標y=k%n;〃得到y(tǒng)坐標if(cMap[x][y]=='.'&&CanPut(x,y)){cMap[x][y]='O'; 〃放炮solve(k+1,current+1); 〃進入下一個坐標，數目加一cMap[x][y]='.'; 〃還原}solve(k+1,current); 〃很技術，你可以選擇也可以不先擇}}intmain(){freopen("input.txt”,"r”,stdin);freopen("output.txt”,"w”,stdout);inti,j;while(scanf("%d”,&n)&&n){for(i=0;i<n;i++){for(j=0;j<n;j++){cin>>cMap[i][j];}}iBest=0; //不要忘了初始化solve(0,0);printf("%d\n”,iBest);}}ZOJProblemSet-1008GnomeTetravexTimeLimit:10SecondsMemoryLimit:32768KBHartisengagedinplayinganinterestinggame,GnomeTetravex,thesedays.Inthegame,atthebeginning,theplayerisgivenn*nsquares.Eachsquareisdividedintofourtrianglesmarkedfournumbers(rangefrom0to9).Inasquare,thetrianglesarethelefttriangle,thetoptriangle,therighttriangleandthebottomtriangle.Forexample,Fig.1showstheinitialstateof2*2squares.Fig.1Theinitialstatewith2*2squaresTheplayerisrequiredtomovethesquarestotheterminationstate.Intheterminationstate,anytwoadjoiningsquaresshouIdmaketheadjacenttrianglemarkedwiththesamenumber.Fig.2showsoneoftheterminationstatesoftheaboveexample.Fig.2OneterminationstateoftheaboveexampleItseemsthegameisnotsohard.Butindeed,Hartisnotaccomplishedinthegame.Hecanfinishtheeasiestgamesuccessfully.Whenfacingwithamorecomplexgame,hecanfindnowayout.Oneday,whenHartwasplayingaverycomplexgame,hecriedout,"Thecomputerismakingagooseofme.It'simpossibletosolveit."Tosuchapoorplayer,thebestwaytohelphimistotellhimwhetherthegamecouldbesolved.Ifheistoldthegameisunsolvable,heneedn'twastesomuchtimeonit.InputTheinputfileconsistsofseveralgamecases.Thefirstlineofeachgamecasecontainsoneintegern,0<=n<=5,indicatingthesizeofthegame.Thefollowingn*nlinesdescribethemarkingnumberofthesetriangles.Eachlineconsistsoffourintegers,whichinorderrepresentthetoptriangle,therighttriangle,thebottomtriangleandthelefttriangleofonesquare.Afterthelastgamecase,theinteger0indicatestheterminationoftheinputdataset.OutputYoushouldmakethedecisionwhetherthegamecasecouldbesolved.Foreachgamecase,printthegamenumber,acolon,andawhitespace,thendisplayyourjudgment.Ifthegameissolvable,printthestring"Possible".Otherwise,pleaseprint"Impossible"toindicatethatthere'snowaytosolvetheproblem.Printablanklinebetweeneachgamecase.Note:Anyunwantedblanklinesorwhitespacesareunacceptable.SampleInput2TOC\o"1-5"\h\z9144456854044321112223334440OutputfortheSampleInputGame1:PossibleGame2:ImpossibleCode:#include<stdio.h>intn; 〃方格矩陣的大小intq; 〃方格的類型數intiSquare[25][4];//方格矩陣，類型相同的只存一個intiCount[25]; //存放方格的類型，因為方格數最多25個intiTable[25]; 〃存放解決方案，實際放置的方格〃判斷函數，是否能把方格放下intPlace(intiPos){inti;if(iPos==n*n)return1; //n*n個方格都可以放下，返回值為真〃對q種類型，每個都往ipos的位置放一下試試for(i=0;i<q;i++){if(iCount[i]==0)continue;〃該種類型方格已經用完if(iPos%n!=0)//不是最左邊的if(iSquare[iTable[iPos-1]][1]!=iSquare[i][3])continue;if(iPos>=n)//不是最上邊的if(iSquare[iTable[iPos-n]][2]!=iSquare[i][0])continue;iTable[iPos]=i;iCount[i]--;if(Place(iPos+1)==1)return1;//dfs的精髓！?。。。?！〃恢復該方格的類型數1個，便于下一次搜索iCount[i]++;}