P16050 [ICPC 2022 NAC] Tic Tac Toe CountingLink: https://www.luogu.com.cn/problem/P16050题目描述井字棋是一种简单的儿童游戏。它在一个3 × 3 3 \times 33×3的网格上进行。第一名玩家在9 99个格子中的任意一个放置 X。下一名玩家在剩下的8 88个格子中的任意一个放置 O。玩家们轮流在空格中交替放置 X 和 O直到某名玩家的符号连成一条线或者网格被填满为止。如果某名玩家在任意一行、一列或两条对角线中的任意一条上连成三个自己的符号则该玩家获胜游戏结束。弗雷德和萨姆正在玩一局井字棋。在游戏进行到中途时弗雷德产生了疑问“从这个局面继续往下进行的所有对局中有多少局是 X 获胜有多少局是 O 获胜”如果两局游戏的落子顺序不同则视为不同的对局即使它们在某个时刻的网格局面完全相同。给定若干网格局面首先判断它们是否能在井字棋对局中达到如果能够达到则计算从这个局面开始包含该局面的所有后续对局中X 获胜的对局数和 O 获胜的对局数。输入格式输入的第一行包含一个整数t tt1 ≤ t ≤ 10 5 1 \le t \le 10^51≤t≤105表示测试用例的网格数量。接下来的t tt行每行包含一个字符串s ss∣ s ∣ 9 |s| 9∣s∣9字符串仅由字符 ‘.’、‘X’ 和/或 ‘O’ 组成。这些是测试用例的网格。前三个字符表示第一行接下来三个字符表示第二行最后三个字符表示最后一行其中 ‘.’ 表示空格。例如字符串XX..O....表示以下网格输出格式对于每个测试用例输出两个空格分隔的整数。如果该网格在井字棋对局中无法达到则输出− 1 -1−1− 1 -1−1。如果该网格可以达到则输出从这个局面开始包含该局面的所有对局中 X 获胜的数量随后输出 O 获胜的数量。输入输出样例 #1输入 #14 XX..O.... X...OX... OOOX.X.X. OOOXXX...输出 #1191 194 232 200 0 1 -1 -1Solution1. 题意输入若干组井字棋的残局状态求从这个状态起衍生出的O和X获胜的不同的局面数。2. 分析首先把− 1 -1−1判掉。一个合法的局面必须满足什么X的数量等于O的数量或比O多1 11不可能双方都连成线样例里就有如果X已获胜则X的数量必须比O多1 11如果O已获胜则X的数量必须等于O的数量。局面合法的情况下就开始递归顺着往里下子往下记忆化搜索直到一方获胜或者平局。如果推到最后X获胜那就把( 1 , 0 ) (1,0)(1,0)加到倒数第二个状态上O获胜就把( 0 , 1 ) (0,1)(0,1)加到倒数第二个状态上都没获胜就不处理。然后从倒数第二个状态开始倒着往回推就可以了倒数第二个状态已经被加上了终局的胜负种类数因此从倒数第二个状态引出的胜负局势数量会随着回溯过程逐渐累加和传播到前面的状态。如此一来递归函数内层返回的一对数值就是上一步上一层递归调用的状态能够引出的后序的胜负局面数量。到这里思路就很明确了因为答案是回溯阶段“反向传播”的因此回溯到某个状态时说明这个状态的后序胜负种类数已经计算完毕将计算完毕的答案“缓存”起来后续就能O ( 1 ) O(1)O(1)的时间复杂度完成一次查询。特别地你也可以把不合法局面的− 1 -1−1如同黑名单一样跟着缓存起来代码里没有。3. 代码importsys sys.setrecursionlimit(25000)defwin(board,player):lines[(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]fora,b,cinlines:ifboard[a]board[b]board[c]player:returnTruereturnFalsememo{}defsolve(board):ifboardinmemo:returnmemo[board]cntxboard.count(X)cntoboard.count(O)xwinwin(board,X)owinwin(board,O)ifxwin:res(1,0)elifowin:res(0,1)elifcntxcnto9:res(0,0)else:turnXifcntxcntoelseOrx,ro0,0fori,chinenumerate(board):ifch.:next_boardboard[:i]turnboard[i1:]nx,nosolve(next_board)rxnx rono res(rx,ro)memo[board]resreturnresdefvalid(board):cntxboard.count(X)cntoboard.count(O)ifnot(cntxcntoorcntxcnto1):returnFalsexwinwin(board,X)owinwin(board,O)ifxwinandowin:returnFalseifxwinandcntx!cnto1:returnFalseifowinandcntx!cnto:returnFalsereturnTruedefmain():input_datasys.stdin.read().split()iteratoriter(input_data)tint(next(iterator))for_inrange(t):snext(iterator)ifnotvalid(s):print(-1 -1)else:ansx,ansosolve(s)print(f{ansx}{anso})main()