《TicTacToe》解题报告.doc

Tic Tac Toe（POJ2361）By sx349 【问题描述】Tic Tac Toe is a game played on a 3 by 3 grid. Tic Tac Toe是一个在3*3大小的棋盘上玩的游戏。One player, X, starts by placing an X at an unoccupied grid position. Then the other player, O, places an O at an unoccupied grid position. 一个玩家X，现在棋盘上空着的位置放入一个X。接着，另一个玩家O，在棋盘上另一个空着的位置放入一个O。Play alternates between X and O until the grid is filled or one players symbols occupy an entire line (vertical, horizontal, or diagonal) in the grid. X和O轮流放置，直到棋盘被填满或者任意一方的标志形成了填满了一横行或一纵行或任意一条对角线。We will denote the initial empty Tic Tac Toe grid with nine dots. Whenever X or O plays we fill in an X or an O in the appropriate position. The example below illustrates each grid configuration from the beginning to the end of a game in which X wins. 空白的棋盘将用九个“.”表示。当X或O放置时，我们在相应的位置放入一个X或O。下面的例子显示了从开始到游戏结束，X获胜的一系列棋盘态势。. X. X.O X.O X.O X.O X.O X.O. . . . .O. .O. OO. OO. . . .X .X X.X X.X XXXYour job is to read a grid and to determine whether or not it could possibly be part of a valid Tic Tac Toe game. That is, is there a series of plays that can yield this grid somewhere between the start and end of the game? 你的工作是读入一个棋盘，然后判断这是否可能是一个有效的Tic Tac Toe游戏的一部分，也即是否有一系列放置使得这个棋盘态势在某局游戏过程中能够被摆出来。【输入】The first line of input contains N, the number of test cases. 4N-1 lines follow, specifying N grid configurations separated by empty lines.第一行包括一个数N，是测试数据个数。接下来4N-1行，用空格隔开分别说明了N个棋盘布局。【输出】For each case print yes or no on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game.对所有测试数据，在每一行输出“yes”或“no”，表示这个布局是某个Tic Tac Toe游戏的一部分。【样例输入输出】Sample InputSample Output2X.OOO.XXXO.XXX.OOO yesno【问题分析】本题的大意为判断某状态是否可由一系列规则从空状态改变而来。从最直观的方面来说，我们可以根据当前的状态向前搜索。因为我们知道每一步是由谁走的，因此，首先判断棋盘上的棋子个数是否满足要求，然后，倒序枚举每一步棋子的位置。显然，每一步最多枚举的个数是5个，而总共枚举的步数最多只有9步，因此这个算法的时间复杂度还是很低的。但是，由于N没有给定，为了防止N很大导致的超时（虽然基本上不可能出现这样的情况），我们稍微改变一下思维方式：根据这一系列的规则，构造出所有可行的状态，再进行判断。以步数为值进行深搜，每次枚举放置的格子，一旦判断游戏结束，则回溯。因为可能是在游戏中的某一步的状态，因此每一步所得到的游戏状态都进行记录。而已经判定可行的游戏状态也可以直接回溯。【算法实现】主要算法流程在问题分析中已说明。在实现的过程中，本打算用一个Longint并借助位运算进行计算，但是由于每个格子的状态在操作和读入都有三种而非两种（“.”也是一种），因此只能逐位的开了个九维数组。【参考程序】时间复杂度： C为常数，可认为约为； 空间复杂度：； Pascal参考程序：PROG: P2361LANG: PASCALID: szxyjProgram P2361;Var N,I,J:Longint; S,Q:Array1.9 of Integer; F:Array-1.1,-1.1,-1.1,-1.1,-1.1,-1.1,-1.1,-1.1,-1.1 of Boolean; St,T:String;Function Check:Boolean;BeginExit(FS1,S2,S3,S4,S5,S6,S7,S8,S9);End;Procedure Search(K:Longint);Var I:Longint;Function Check1:Boolean;VarI,J:Longint;BeginIf ABS(Q1+Q4+Q7)=3 Then Exit(True);If ABS(Q2+Q5+Q8)=3 Then Exit(True);If ABS(Q3+Q6+Q9)=3 Then Exit(True);If ABS(Q1+Q2+Q3)=3 Then Exit(True);If ABS(Q4+Q5+Q6)=3 Then Exit(True);If ABS(Q7+Q8+Q9)=3 Then Exit(True);If ABS(Q1+Q5+Q9)=3 Then Exit(True);If ABS(Q3+Q5+Q7)=3 Then Exit(True);Exit(False);End;BeginFQ1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9:=True;If Check1 Then Exit;For I:=1 to 9 do BeginIf QI=0 Then BeginIf Odd(K) Then QI:=1 Else QI:=-1;Search(K+1);QI:=0;End;End;End;BeginReadln(N);Fillchar(Q,Sizeof(Q),0);Fillchar(F,Sizeof(F),False);Search(1);For I:=1 to N do BeginReadln(St);While St= do Readln(