资源描述：
《《tictactoe》解题报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、TicTacToe（POJ2361）Bysx349【问题描述】TicTacToeisagameplayedona3by3grid.TicTacToe是一个在3*3大小的棋盘上玩的游戏。Oneplayer,X,startsbyplacinganXatanunoccupiedgridposition.Thentheotherplayer,O,placesanOatanunoccupiedgridposition.一个玩家X，现在棋盘上空着的位置放入一个X。接着，另一个玩家O，在棋盘上另一个空着的位置放入一个O。Pl
2、ayalternatesbetweenXandOuntilthegridisfilledoroneplayer'ssymbolsoccupyanentireline(vertical,horizontal,ordiagonal)inthegrid.X和O轮流放置，直到棋盘被填满或者任意一方的标志形成了填满了一横行或一纵行或任意一条对角线。WewilldenotetheinitialemptyTicTacToegridwithninedots.WheneverXorOplayswefillinanXoranOin
3、theappropriateposition.TheexamplebelowillustrateseachgridconfigurationfromthebeginningtotheendofagameinwhichXwins.空白的棋盘将用九个“.”表示。当X或O放置时，我们在相应的位置放入一个X或O。下面的例子显示了从开始到游戏结束，X获胜的一系列棋盘态势。...X..X.OX.OX.OX.OX.OX.O.............O..O.OO.OO............X..XX.XX.XXXXYour
4、jobistoreadagridandtodeterminewhetherornotitcouldpossiblybepartofavalidTicTacToegame.Thatis,isthereaseriesofplaysthatcanyieldthisgridsomewherebetweenthestartandendofthegame?你的工作是读入一个棋盘，然后判断这是否可能是一个有效的TicTacToe游戏的一部分，也即是否有一系列放置使得这个棋盘态势在某局游戏过程中能够被摆出来。【输入】Thefi
5、rstlineofinputcontainsN,thenumberoftestcases.4N-1linesfollow,specifyingNgridconfigurationsseparatedbyemptylines.第一行包括一个数N，是测试数据个数。接下来4N-1行，用空格隔开分别说明了N个棋盘布局。【输出】Foreachcaseprint"yes"or"no"onalinebyitself,indicatingwhetherornottheconfigurationcouldbepartofaTic
6、TacToegame.对所有测试数据，在每一行输出“yes”或“no”，表示这个布局是某个TicTacToe游戏的一部分。【样例输入输出】SampleInputSampleOutput2X.OOO.XXXO.XXX.OOOyesno【问题分析】本题的大意为判断某状态是否可由一系列规则从空状态改变而来。从最直观的方面来说，我们可以根据当前的状态向前搜索。因为我们知道每一步是由谁走的，因此，首先判断棋盘上的棋子个数是否满足要求，然后，倒序枚举每一步棋子的位置。显然，每一步最多枚举的个数是5个，而总共枚举的步数最多只
7、有9步，因此这个算法的时间复杂度还是很低的。但是，由于N没有给定，为了防止N很大导致的超时（虽然基本上不可能出现这样的情况），我们稍微改变一下思维方式：根据这一系列的规则，构造出所有可行的状态，再进行判断。以步数为值进行深搜，每次枚举放置的格子，一旦判断游戏结束，则回溯。因为可能是在游戏中的某一步的状态，因此每一步所得到的游戏状态都进行记录。而已经判定可行的游戏状态也可以直接回溯。【算法实现】主要算法流程在问题分析中已说明。在实现的过程中，本打算用一个Longint并借助位运算进行计算，但是由于每个格子的状态在
8、操作和读入都有三种而非两种（“.”也是一种），因此只能逐位的开了个九维数组。【参考程序】时间复杂度：C为常数，可认为约为；空间复杂度：；Pascal参考程序：{PROG:P2361LANG:PASCALID:szxyj}ProgramP2361;VarN,I,J:Longint;S,Q:Array[1..9]ofInteger;F:Array[-1..1,-1..1,-1..1,-1.
