竞彩网站建设怎么给自己网站做搜索框

竞彩网站建设,怎么给自己网站做搜索框,个人信息查询系统官网,移动网站建设模板题目翻译 考虑以下简化版国际象棋#xff1a;我们有一个 444 \times 444 的棋盘#xff0c;第一行#xff08;输入中的最下方#xff09;有四个白兵#xff0c;最后一行#xff08;输入中的最上方#xff09;有四个黑兵。游戏的目标是让自己的一个兵走到对方底线#x…题目翻译考虑以下简化版国际象棋我们有一个4×44 \times 44×4的棋盘第一行输入中的最下方有四个白兵最后一行输入中的最上方有四个黑兵。游戏的目标是让自己的一个兵走到对方底线白方走到最后一行黑方走到第一行或者逼对手无棋可走即“困毙”。当轮到某玩家走棋时若他没有合法走法包括所有兵已被吃光则他被困毙。兵的走法与普通国际象棋相同但不能一次走两步。即兵可以向前朝向对方底线走一步前提是目标格为空。兵也可以吃掉对方兵如果对方兵位于其左前方或右前方斜前方一格。被吃的兵从棋盘移除。给定棋盘上兵的位置假设双方都采取最优策略判断谁会获胜。同时需要计算游戏结束前会进行的步数假设获胜方会尽快获胜输的一方会尽可能拖延。输入局面总是轮到白方走子。输入格式第一行输入测试用例数最多505050个。每个用例包含四行描述棋盘前面有一个空行。四行中的第一行表示棋盘的最后一行黑兵的起始位置。黑兵用p表示白兵用P表示空位用.表示。每方有111到444个兵。初始局面不会是终局局面且白方至少有一个合法走子。注意输入局面不一定是从初始局面合法走出来的。输出格式对于每个测试用例输出一行如果白方赢输出white (xx)如果黑方赢输出black (xx)其中xx是步数白方赢时步数为奇数黑方赢时为偶数。题目分析与解题思路本题是一个双方零和博弈问题棋盘大小固定为4×44 \times 44×4每方最多444个兵状态空间有限适合用极小化极大算法Minimax\texttt{Minimax}Minimax配合记忆化搜索解决。核心思路状态表示棋盘共有161616格每格有三种状态空、白兵、黑兵。可以用222位二进制表示一格000000空010101白兵101010黑兵整个棋盘用一个646464位整数unsigned long long表示。另外还需要记录当前轮到谁走000白方111黑方。胜负判定白方赢任意白兵到达第000行黑方底线。黑方赢任意黑兵到达第333行白方底线。若当前玩家无合法走法包括无兵可走则对方赢。走法生成根据当前玩家白方或黑方遍历所有兵向前走检查目标格是否在棋盘内且为空。吃子检查左前、右前对白方是行减111对黑方是行加111是否有对方兵。搜索策略Minimax\texttt{Minimax}Minimax设solve(state,turn)solve(state, turn)solve(state,turn)返回赢家从当前状态到游戏结束的步数其中turn0turn 0turn0表示白方走turn1turn 1turn1表示黑方走。终止条件出现胜负局面或无棋可走。递归过程生成所有合法走法。对每个走法递归调用solve(nextState,turn⊕1)solve(nextState, turn \oplus 1)solve(nextState,turn⊕1)。如果当前玩家能赢则选择步数最少的走法尽快赢。如果当前玩家会输则选择步数最多的走法拖延。记忆化用哈希表缓存(state,turn)(state, turn)(state,turn)的结果避免重复计算。算法流程读入棋盘转换为646464位状态码。调用solve(state,0)solve(state, 0)solve(state,0)白方先走。根据返回的赢家和步数输出结果。复杂度分析状态数每格333种状态最多316≈4.3×1073^{16} \approx 4.3 \times 10^7316≈4.3×107但实际可达状态远少于这个数每方最多444个兵。每个状态生成走法最多4×3124 \times 3 124×312种444个兵每个兵最多333种走法向前、左吃、右吃。记忆化后每个状态只计算一次整体在时间和空间上均可接受。代码实现// The Pawn Chess// UVa ID: 10838// Verdict: Accepted// Submission Date: 2025-12-14// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 棋盘编码每格 2 位共 16 格64 位整数存储// 00: 空, 01: 白兵(P), 10: 黑兵(p)constintWHITE1,BLACK2;constintINF1e9;// 方向白兵向上(row-1)黑兵向下(row1)constintWHITE_DIR-1,BLACK_DIR1;constintCAPTURE_DIRS[2][2]{{-1,-1},{-1,1}};// 白兵吃子方向左上、右上constintBLACK_CAPTURE_DIRS[2][2]{{1,-1},{1,1}};// 黑兵吃子方向左下、右下// 记忆化缓存map状态, pair结果, 步数unordered_mapunsignedlonglong,pairint,intmemo[2];// 0:白方走, 1:黑方走// 从状态中获取某格的值intgetCell(unsignedlonglongstate,intr,intc){intpos(r*4c)*2;return(statepos)3;}// 设置某格的值voidsetCell(unsignedlonglongstate,intr,intc,intval){intpos(r*4c)*2;state~(3ULLpos);state|((unsignedlonglong)valpos);}// 判断是否到达底线boolisWhiteWin(unsignedlonglongstate){for(intc0;c4;c)if(getCell(state,0,c)WHITE)returntrue;// 白兵到达第0行黑方底线returnfalse;}boolisBlackWin(unsignedlonglongstate){for(intc0;c4;c)if(getCell(state,3,c)BLACK)returntrue;// 黑兵到达第3行白方底线returnfalse;}// 生成所有合法走法vectorpairunsignedlonglong,intgenerateMoves(unsignedlonglongstate,intturn){vectorpairunsignedlonglong,intmoves;intplayer(turn0)?WHITE:BLACK;intdir(turn0)?WHITE_DIR:BLACK_DIR;for(intr0;r4;r){for(intc0;c4;c){if(getCell(state,r,c)!player)continue;// 向前走一步intnrrdir;if(nr0nr4getCell(state,nr,c)0){unsignedlonglongnextstate;setCell(next,r,c,0);setCell(next,nr,c,player);moves.push_back({next,1});}// 吃子autocapDirs(turn0)?CAPTURE_DIRS:BLACK_CAPTURE_DIRS;for(autod:capDirs){intnrrd[0];intnccd[1];if(nr0nr4nc0nc4){inttargetgetCell(state,nr,nc);if(target!0target!player){unsignedlonglongnextstate;setCell(next,r,c,0);setCell(next,nr,nc,player);moves.push_back({next,1});}}}}}returnmoves;}// Minimax 搜索返回 (胜负, 步数)pairint,intsolve(unsignedlonglongstate,intturn){// 检查缓存if(memo[turn].count(state))returnmemo[turn][state];// 终局判断if(isWhiteWin(state))return{0,0};// 白方赢步数为0当前还未走if(isBlackWin(state))return{1,0};// 黑方赢automovesgenerateMoves(state,turn);if(moves.empty()){// 当前玩家无棋可走对方赢if(turn0)return{1,0};// 白方无棋黑方赢elsereturn{0,0};// 黑方无棋白方赢}intbestWinner-1;intbestStepsINF;intworstSteps-1;for(automv:moves){autoressolve(mv.first,turn^1);intwinnerres.first;intstepsres.secondmv.second;// 加上这一步if(bestWinner-1){bestWinnerwinner;bestStepssteps;worstStepssteps;}else{if(winnerturn){// 当前玩家能赢取最短步数if(winnerbestWinner)bestStepsmin(bestSteps,steps);else{bestWinnerwinner;bestStepssteps;}}else{// 当前玩家会输取最长步数拖延if(bestWinnerwinner)worstStepsmax(worstSteps,steps);else{// 如果之前有赢的可能保留赢法if(bestWinner!turn){bestWinnerwinner;worstStepssteps;}}}}}intfinalSteps(bestWinnerturn)?bestSteps:worstSteps;memo[turn][state]{bestWinner,finalSteps};return{bestWinner,finalSteps};}intmain(){intT;cinT;while(T--){vectorstringboard(4);for(inti0;i4;i){cinboard[i];// 处理可能的空格样例中有空格但实际输入可能没有if(board[i].size()4)board[i]....;}// 构建状态unsignedlonglongstate0;for(intr0;r4;r){for(intc0;c4;c){intval0;if(board[r][c]P)valWHITE;elseif(board[r][c]p)valBLACK;setCell(state,r,c,val);}}// 初始化缓存memo[0].clear();memo[1].clear();autoressolve(state,0);intwinnerres.first;intstepsres.second;if(winner0)coutwhite (steps)\n;elsecoutblack (steps)\n;}return0;}总结本题是一道典型的博弈搜索题通过状态压缩和记忆化搜索可以在有限时间内求解。关键在于理解Minimax\texttt{Minimax}Minimax搜索中“赢方尽快、输方拖延”的策略并正确实现走法生成与胜负判断。代码中使用了646464位整数表示棋盘状态提高了存储和计算效率适合题目给定的数据范围。