题目描述“滑梯与梯子”Chutes and Ladders\texttt{Chutes and Ladders}Chutes and Ladders是一款儿童棋盘游戏。棋盘上有编号为111到100100100的方格玩家计数器从虚拟的000号方格开始。每位玩家轮流掷一枚111到666的骰子并将计数器向前移动对应的格数。第一个到达100100100号方格的玩家获胜。棋盘上存在“梯子”连接低编号到高编号和“滑梯”连接高编号到低编号。如果玩家落在梯子或滑梯的起始格则立即移动到对应的终点格仅起始格有效。此外有些方格会触发“失去下一回合”或“额外再掷一次”的效果。若玩家位于959595号或更高方格则掷出的点数若导致超过100100100则本次移动无效即停留在原地。所有游戏共用同一组骰子点数序列每场游戏从序列开头开始使用。本题给定一组骰子点数以000结束和若干场游戏描述每场以玩家数开始以玩家数000结束要求输出每场游戏的获胜玩家编号。输入格式输入的第一部分是一组骰子点数由若干个111到666的整数组成以单个000结束。之后是若干场游戏描述。每场游戏描述的第一行为玩家数ppp1p61 p 61p6。随后若干行定义梯子和滑梯每行两个整数aaa、bbb表示从aaa到bbb的连接若aba bab则为梯子否则为滑梯以000000结束。接下来若干行定义特殊方格每行一个整数xxx若x0x 0x0表示额外回合方格若x0x 0x0表示失去回合方格其绝对值即为方格编号以000结束。游戏描述以玩家数000结束。所有骰子点数总和保证足够完成所有游戏。输出格式对于每场游戏输出一行一个整数表示获胜玩家的编号从111开始计数。样例输入3 6 3 2 5 1 3 4 2 3 1 2 0 2 6 95 99 1 0 0 -3 98 0 2 3 99 6 90 0 0 0 0输出2 2题目分析本题是标准的棋盘游戏模拟。由于玩家数不超过555骰子点数序列长度小于100010001000且每场游戏保证在序列结束前产生胜者因此可以直接按顺序模拟每场游戏。关键点在于处理梯子/滑梯的即时移动、失去回合和额外回合的逻辑以及959595格以上的越界规则。模拟时需维护每位玩家的当前位置、是否处于失去回合状态以及当前使用的骰子点数索引所有游戏共享同一序列但每场游戏从头开始。每轮按玩家顺序依次处理直到某玩家到达100100100号方格。解题思路读取骰子点数序列持续读取整数直到遇到000存入向量throwings。循环处理每场游戏读取玩家数players若为000则结束。初始化方格信息数组squares[101]包含ladder_end若该格为梯子起始则存储终点否则为000。chute_end若该格为滑梯起始则存储终点否则为000。lose_turn布尔值表示是否失去下一回合。extra_turn布尔值表示是否额外再掷一次。读入梯子/滑梯循环读取两个整数start和end若均为000则结束。若start end则为梯子设置squares[start].ladder_end end否则为滑梯设置squares[start].chute_end end。读入特殊方格循环读取整数x若为000则结束。若x0x 0x0设置squares[x].extra_turn 1否则设置squares[abs(x)].lose_turn 1。模拟游戏初始化position[6] {0}miss_turn[6] {0}骰子索引idx 0。外层while循环直到idx超出序列范围但题目保证会提前结束。内层for循环遍历玩家111到players若miss_turn[i]为真则跳过本回合重置miss_turn[i] 0idx继续下一位玩家。否则取当前骰子点数die throwings[idx]。若position[i] 95且position[i] die 100则本次移动无效idx继续下一位玩家。否则计算新位置next position[i] die更新position[i] next。检查next是否有梯子或滑梯若squares[next].ladder_end 0则position[i] squares[next].ladder_end若squares[next].chute_end 0则position[i] squares[next].chute_end。检查特殊方格若squares[next].lose_turn则设置miss_turn[i] 1若squares[next].extra_turn则将循环变量i减111使当前玩家再掷一次。若position[i] 100则输出玩家编号i并将idx置为序列长度以退出所有循环。最后idx移动到下一个骰子点数。复杂度分析每场游戏模拟的回合数不超过骰子点数序列长度1000 10001000玩家数≤5\le 5≤5因此单场游戏时间复杂度O(T⋅p)O(T \cdot p)O(T⋅p)总时间极短。空间复杂度O(101)O(101)O(101)用于存储棋盘信息。代码实现// Chutes and Ladders// UVa ID: 647// Verdict: Accepted// Submission Date: 2017-05-31// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structsquare{intlose_turn,extra_turn,ladder_end,chute_end;};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);vectorintthrowings;intnumber;while(cinnumber,number0)throwings.push_back(number);intplayers;while(cinplayers,players0){square squares[110];memset(squares,0,sizeof(squares));intstart,end;while(cinstartend){if(start0end0)break;if(startend)squares[start].ladder_endend;elsesquares[start].chute_endend;}while(cinstart,start!0){if(start0)squares[start].extra_turn1;elsesquares[abs(start)].lose_turn1;}intposition[8]{0},miss_turn[8]{0},idx0;while(idxthrowings.size()){for(inti1;iplayers;i){intcurrenti;if(miss_turn[i]){miss_turn[i]0,idx;continue;}intdiethrowings[idx];if(position[i]95position[i]die100)continue;intnextposition[i]die;position[i]next;if(squares[next].ladder_end0)position[i]squares[next].ladder_end;if(squares[next].chute_end0)position[i]squares[next].chute_end;if(squares[next].lose_turn)position[i]next,miss_turn[i]1;if(squares[next].extra_turn)position[i]next,i-1;if(position[current]100){coutcurrent\n;idxthrowings.size();break;}idx;}}}return0;}总结本题是典型的模拟题按照游戏规则逐步模拟即可。关键点包括区分梯子、滑梯的起始和终点正确更新位置。正确处理失去回合和额外回合的逻辑注意额外回合需让当前玩家再掷一次循环变量减111即可。处理959595格以上的越界无效掷骰。共用骰子序列每场游戏从头开始使用。注意输入格式中特殊方格可能包含负数。该模拟方法清晰直观适合作为模拟题的练习。