题目描述
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），排列成十字形。游戏开始时，某些孔中有木钉，其他孔为空。游戏规则：将一个木钉水平或垂直跳过相邻的木钉，落入空孔，被跳过的木钉被移除。
给定初始配置，按以下规则模拟游戏：
- 始终选择目标孔编号最大的合法移动
- 如果多个移动有相同的最大目标孔，选择源孔编号最大的移动
- 重复直到没有合法移动
- 输出剩余木钉所在孔的编号之和
输入格式
第一行包含整数NNN（1≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 移动结构体：源孔、中间孔、目标孔structjump{intfrom,middle,to;booloperator<(constjump&another)const{if(to!=another.to)returnto>another.to;// 目标孔大的优先elsereturnfrom>another.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);// 预生成所有合法移动vector<jump>jumps;for(inti=0;i<7;i++)for(intj=0;j<7;j++)if(board[i][j]){for(intk=0;k<4;k++){intni=i+offset[k][0],nj=j+offset[k][1];intnni=ni+offset[k][0],nnj=nj+offset[k][1];if(ni>=0&&ni<7&&nj>=0&&nj<7&&nni>=0&&nni<7&&nnj>=0&&nnj<7&&board[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];cin>>N;cout<<"HI Q OUTPUT"<<endl;for(inti=1;i<=N;i++){// 初始化：全部为空memset(holes,0,sizeof(holes));// 读取初始有木钉的孔while(cin>>hole,hole)holes[hole]=1;// 模拟游戏while(true){boolupdated=false;for(auto&j:jumps)if(holes[j.from]&&holes[j.middle]&&!holes[j.to]){updated=true;holes[j.from]=0;holes[j.middle]=0;holes[j.to]=1;break;// 每次只执行优先级最高的一个移动}if(!updated)break;}// 计算剩余木钉的编号之和intsumOfHoles=0;for(inti=1;i<=33;i++)if(holes[i])sumOfHoles+=i;cout<<sumOfHoles<<endl;}cout<<"END OF OUTPUT"<<endl;return0;}
