2026年【江苏“信息与未来”编程思维】真题及题解T6桌面游戏题目描述Dr. X 设计了一个双人桌面游戏在一个3 × 3 3 \times 33×3的方格中轮流填入数字1 , 2 , … , 9 1, 2, \ldots, 91,2,…,9。现在方格中已经填好了一部分数字Dr. X 和 Dr. Y 按如下规则交替填入数字 (Dr. X 先填)每一轮从当前剩余未使用的数字中找到最小的一个数字。选择方格中的任意一个空位将该数字填入。换另一个人重复这一过程当方格被填满时游戏结束。游戏结束后双方计算分数的规则Dr. X 的分数x xx等于三行数字乘积之和。Dr. Y 的分数y yy等于三列数字乘积之和。Dr. X 和 Dr. Y 都希望拉开和对方分数的差距Dr. X 希望最大化x − y x - yx−y而 Dr. Y 希望最小化x − y x - yx−y。他们都互相知道对方都是绝顶聪明的人一定会采取对自己最有利的策略。请你写程序预判游戏的最终结果若 Dr. X 的分数更高输出first \texttt{first}first若 Dr. Y 的分数更高输出second \texttt{second}second若两人分数相同输出tie \texttt{tie}tie。输入格式第一行输入一个整数T TT表示数据组数。接下来包含T TT组数据。每组数据包含3 33行每行3 33个整数表示当前的3 × 3 3 \times 33×3方格其中0 00表示该位置为空。输入数据保证初始方格中所有非零数字互不相同且都在1 11到9 99之间。输出格式对于每组数据输出一行字符串表示最终结果。输入输出样例 1输入 13 1 2 3 4 5 6 7 8 0 1 4 7 2 5 8 3 6 0 1 4 7 2 5 8 0 6 0输出 1first second second输入输出样例 2输入 21 0 0 3 4 5 6 7 0 9输出 2tie说明/提示样例 1 解释第一组数据中只有一个空位剩余数字为9 99先手只能将9 99填入右下角。此时 Dr. X 的分数为1 × 2 × 3 4 × 5 × 6 7 × 8 × 9 630 1 \times 2 \times 3 4 \times 5 \times 6 7 \times 8 \times 9 6301×2×34×5×67×8×9630Dr. Y 的分数为1 × 4 × 7 2 × 5 × 8 3 × 6 × 9 270 1 \times 4 \times 7 2 \times 5 \times 8 3 \times 6 \times 9 2701×4×72×5×83×6×9270因此先手获胜。第二组数据中只有一个空位剩余数字同样为9 99。先手填入后Dr. X 的分数为270 270270Dr. Y 的分数为630 630630因此后手获胜。第三组数据中剩余数字为3 33和9 99。先手必须先填入3 33后手再填入9 99。无论先手如何选择位置后手都能使自己的最终分数更高因此后手必胜。样例 2 解释这一组的剩余数字为1 11、2 22、8 88。先手若不把1 11填在左上角后手就能获胜因此先手的最优选择是先填左上角。之后后手把2 22填在第三行第二列先手再把8 88填在第一行第二列最终方格为1 8 3 4 5 6 7 2 9此时 Dr. X 的分数为1 × 8 × 3 4 × 5 × 6 7 × 2 × 9 270 1 \times 8 \times 3 4 \times 5 \times 6 7 \times 2 \times 9 2701×8×34×5×67×2×9270Dr. Y 的分数为1 × 4 × 7 8 × 5 × 2 3 × 6 × 9 270 1 \times 4 \times 7 8 \times 5 \times 2 3 \times 6 \times 9 2701×4×78×5×23×6×9270因此平局。数据规模对于30 % 30\%30%的数据空位0 00的个数不超过2 22。对于60 % 60\%60%的数据空位0 00的个数不超过5 55。对于100 % 100\%100%的数据空位0 00的个数不超过9 991 ≤ T ≤ 20 1 \le T \le 201≤T≤20。思路分析游戏规则中数字的填入顺序是固定的从剩余数字中从小到大依次填入。因此游戏过程可以看作给定当前棋盘和当前步数确定该填哪个数字玩家选择空位填入该数字然后交换回合。棋盘只有3×3 9个格子最多9! 362880种不同的完整填法完全可以通过深度优先搜索DFS枚举所有可能局面。每一步轮到谁由步数的奇偶性决定步数从 0 开始偶数步为先手 Dr.X奇数步为后手 Dr.Y。先手的目标是最大化最终分数差x - y后手的目标是最小化它因此采用极小极大搜索。递归函数返回从当前局面开始双方都采取最优策略下的最终分数差。叶子节点所有空位填满直接计算x - y并返回。复杂度为O(n!)n ≤ 9每组数据最多约 36 万次递归调用T ≤ 20运行时间充裕。代码实现#includebits/stdc.husingnamespacestd;intb[3][3];// 棋盘intrem[10],remCnt;// 剩余数字升序及个数intused[10];// 数字是否已出现在初始棋盘中// 深度优先搜索step 表示已填入数字的个数也是当前要填 rem[step]intdfs(intstep){// 所有空位填满计算最终分数差if(stepremCnt){intx0,y0;for(inti0;i3;i){intp1;for(intj0;j3;j)p*b[i][j];xp;// 三行乘积之和}for(intj0;j3;j){intp1;for(inti0;i3;i)p*b[i][j];yp;// 三列乘积之和}returnx-y;}intvalrem[step];// 本轮必须填入的数字boolisX(step%20);// 偶数步先手奇数步后手intbestisX?-1000000000:1000000000;// 先手取最大后手取最小// 枚举所有空位for(inti0;i3;i){for(intj0;j3;j){if(b[i][j]0){b[i][j]val;// 填入数字intchilddfs(step1);// 递归下一层b[i][j]0;// 回溯if(isX){if(childbest)bestchild;// 先手最大化}else{if(childbest)bestchild;// 后手最小化}}}}returnbest;}intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;while(T--){memset(used,0,sizeof(used));// 读入棋盘标记已出现的数字for(inti0;i3;i){for(intj0;j3;j){cinb[i][j];if(b[i][j])used[b[i][j]]1;}}// 收集剩余数字升序remCnt0;for(inti1;i9;i){if(!used[i])rem[remCnt]i;}intdiffdfs(0);// 最优最终分数差if(diff0)coutfirst\n;elseif(diff0)coutsecond\n;elsecouttie\n;}return0;}功能分析核心算法极小极大搜索 DFS 穷举模拟所有合法的填数过程。状态表示用全局二维数组b记录棋盘用step隐含记录当前轮到谁以及要填哪个数字。效率最多9!种局面每组数据耗时极短。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}