题目描述Hi-Q\texttt{Hi-Q}Hi-Q是一种流行的单人纸牌游戏。游戏板呈十字形有333333个小孔编号如下1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37实际上标准Hi-Q\texttt{Hi-Q}Hi-Q棋盘有333333个孔编号111到333333排列成十字形。游戏开始时某些孔中有木钉其他孔为空。游戏规则将一个木钉水平或垂直跳过相邻的木钉落入空孔被跳过的木钉被移除。给定初始配置按以下规则模拟游戏始终选择目标孔编号最大的合法移动如果多个移动有相同的最大目标孔选择源孔编号最大的移动重复直到没有合法移动输出剩余木钉所在孔的编号之和输入格式第一行包含整数NNN1≤N≤101 \leq N \leq 101≤N≤10表示游戏实例数量。接下来的行描述每个实例按递增顺序列出初始有木钉的孔编号以000结束。输出格式第一行输出HI Q OUTPUT。对于每个实例输出一行包含最终配置中剩余木钉所在孔的编号之和。最后一行输出END OF OUTPUT。样例输入4 10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 0样例输出HI Q OUTPUT 51 0 561 98 END OF OUTPUT题目分析问题的本质这是一个棋盘游戏模拟问题。需要预先生成所有可能的合法移动跳棋规则按优先级顺序选择移动模拟直到无法移动棋盘布局Hi-Q\texttt{Hi-Q}Hi-Q棋盘有333333个孔排列成十字形。孔编号如下1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33实际上标准编号略有不同但代码中使用7×77 \times 77×7网格映射孔编号。移动规则只能水平或垂直移动必须跳过相邻的一个木钉目标孔必须为空被跳过的木钉被移除优先级规则目标孔编号最大相同目标孔时源孔编号最大参考代码// High-Q// UVa ID: 379// Verdict: Accepted// Submission Date: 2016-07-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 移动结构体源孔、中间孔、目标孔structjump{intfrom,middle,to;booloperator(constjumpanother)const{if(to!another.to)returntoanother.to;// 目标孔大的优先elsereturnfromanother.from;// 源孔大的优先}};// 7x7 网格表示棋盘0 表示无效位置intboard[7][7]{{0,0,1,2,3,0,0},{0,0,4,5,6,0,0},{7,8,9,10,11,12,13},{14,15,16,17,18,19,20},{21,22,23,24,25,26,27},{0,0,28,29,30,0,0},{0,0,31,32,33,0,0}};intoffset[4][2]{{0,1},{1,0},{0,-1},{-1,0}};intmain(intargc,char*argv[]){ios::sync_with_stdio(false);// 预生成所有合法移动vectorjumpjumps;for(inti0;i7;i)for(intj0;j7;j)if(board[i][j]){for(intk0;k4;k){intniioffset[k][0],njjoffset[k][1];intnninioffset[k][0],nnjnjoffset[k][1];if(ni0ni7nj0nj7nni0nni7nnj0nnj7board[ni][nj]board[nni][nnj])jumps.push_back({board[i][j],board[ni][nj],board[nni][nnj]});}}// 按优先级排序sort(jumps.begin(),jumps.end());intN,hole,holes[40];cinN;coutHI Q OUTPUTendl;for(inti1;iN;i){// 初始化全部为空memset(holes,0,sizeof(holes));// 读取初始有木钉的孔while(cinhole,hole)holes[hole]1;// 模拟游戏while(true){boolupdatedfalse;for(autoj:jumps)if(holes[j.from]holes[j.middle]!holes[j.to]){updatedtrue;holes[j.from]0;holes[j.middle]0;holes[j.to]1;break;// 每次只执行优先级最高的一个移动}if(!updated)break;}// 计算剩余木钉的编号之和intsumOfHoles0;for(inti1;i33;i)if(holes[i])sumOfHolesi;coutsumOfHolesendl;}coutEND OF OUTPUTendl;return0;}