1 条题解
-
0
分析:
此代码运用的是模拟算法,通过模拟棋盘上棋子的移动规则来计算最终结果。主要是根据给定的棋子位置关系和初始状态,按照特定顺序检查可移动的情况,进行棋子的移动并计算移动带来的数值变化,直到无法再进行移动为止。
解题思路
给定一个类似棋盘的场景,棋盘上有一些初始放置的棋子,每个棋子有对应的编号。目标是通过特定的移动规则,将棋子进行移动,计算每次移动后数值的变化,最终得到一个总和。算法思想是从编号较大的位置开始,按照下、右、左、上的顺序检查每个位置是否可以根据规则进行棋子移动,若可以则进行移动并计算数值变化,不断重复此过程,直到没有位置可以进行移动为止。
解题原理
1.初始化棋盘状态:使用一个布尔数组 board 来表示棋盘上每个位置是否有棋子,初始时将所有位置设为没有棋子,然后根据输入将有棋子的位置标记为 1,并计算初始棋子编号的总和 sum。
2.定义移动规则数组:分别定义了 shang(上)、xia(下)、zuo(左)、you(右)四个数组,用于表示每个位置的棋子按照相应方向移动时,所涉及的其他位置的编号。
3.移动判断与执行:在 solve 函数中,从编号为 33 的位置开始向前遍历。对于每个位置,如果该位置已经有棋子则跳过。然后按照下、右、左、上的顺序检查该位置是否满足移动条件(即相应方向上的两个位置都有棋子)。如果满足条件,则将当前位置标记为有棋子,将相应方向上的两个位置标记为没有棋子,并计算这次移动所带来的数值变化(即相应方向上两个棋子编号之和减去当前位置的编号)。
4.循环计算:在 main 函数中,不断调用 solve 函数进行移动计算,每次将计算得到的数值变化从 sum 中减去,直到 solve 函数返回特定值(表示无法再进行移动)为止,最终输出 sum 的值。
实现步骤
1.输入处理:读取测试用例的数量 n。
2.初始化与输出标题:输出结果的标题 HI Q OUTPUT,对于每个测试用例,调用 init 函数进行棋盘状态的初始化,包括读取棋子的初始位置并标记,计算初始总和。
3.移动计算:通过循环不断调用 solve 函数进行棋子的移动计算,每次根据 solve 函数的返回值更新 sum。
4.输出结果:当无法再进行移动时,输出最终的 sum 值。
5.结束输出:输出结束标记 END OF OUTPUT
c++代码:
#include <stdio.h> #include <string.h> #include <iostream> #include <cstdlib> #include <string> #include <vector> #include <map> using namespace std; bool board[34]; int sum; int FLAG = -233; void init(){ for(int i = 0; i < 34; i++) board[i] = 0; sum = 0; int tmp; while(1){ cin >> tmp; if(!tmp) break; board[tmp] = 1; sum += tmp; } } int shang[34] = {0,0,0,0,1,2,3,0,0,4,5,6,0,0,7,8,9,10,11,12,13,14,15,16,17,18,19,20,23,24,25,28,29,30}; int xia[34] = {0,4,5,6,9,10,11,14,15,16,17,18,19,20,21,22,23,24,25,26,27,0,0,28,29,30,0,0,31,32,33,0,0,0}; int zuo[34] = {0,0,1,2,0,4,5,0,7,8,9,10,11,12,0,14,15,16,17,18,19,0,21,22,23,24,25,26,0,28,29,0,31,32}; int you[34] = {0,2,3,0,5,6,0,8,9,10,11,12,13,0,15,16,17,18,19,20,0,22,23,24,25,26,27,0,29,30,0,32,33,0}; int solve(){ for(int i = 33; i > 0; i--){ //顺序:下,右,左,上 if(board[i]) continue; if(board[xia[xia[i]]] && board[xia[i]]){ board[i] = 1; board[xia[xia[i]]] = 0; board[xia[i]] = 0; return xia[i]+xia[xia[i]]-i; } if(board[you[you[i]]] && board[you[i]]){ board[i] = 1; board[you[you[i]]] = 0; board[you[i]] = 0; return you[i]+you[you[i]]-i; } if(board[zuo[zuo[i]]] && board[zuo[i]]){ board[i] = 1; board[zuo[zuo[i]]] = 0; board[zuo[i]] = 0; return zuo[i]+zuo[zuo[i]]-i; } if(board[shang[shang[i]]] && board[shang[i]]){ board[i] = 1; board[shang[shang[i]]] = 0; board[shang[i]] = 0; return shang[i]+shang[shang[i]]-i; } } return FLAG; } int main(int argc, char **argv){ int n; cin >> n; cout << "HI Q OUTPUT" << endl; while(n--){ init(); int sub; while((sub = solve()) != FLAG){ sum -= sub; } cout << sum << endl; } cout << "END OF OUTPUT" << endl; return 0; }
- 1
信息
- ID
- 526
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者