题目描述一场重要的足球比赛即将在A\texttt{A}A队和B\texttt{B}B队之间展开。B\texttt{B}B队赢得开球权一名球员位于中场位置(0,0)(0,0)(0,0)。A\texttt{A}A队的防守半场是一个边长为2s2s2s的正方形区域中场线与XXX轴重合。该区域被划分为每边2s2s2s个方格的网格球门位于Y2sY 2sY2s直线上占据YYY轴两侧各ggg个方格的宽度。A\texttt{A}A队有nnn名防守球员位于网格交点处。每名球员可以拦截进入其周围ppp个方格范围内的球即覆盖一个以球员为中心、边长为2p2p2p的方形区域。中场位置(0,0)(0,0)(0,0)不会被任何A\texttt{A}A队球员覆盖。B\texttt{B}B队教练希望放置至多nnn名额外的球员不包括开球者在网格交点处通过一系列直线传球只能平行于XXX或YYY轴将球从中场位置移动到A\texttt{A}A队球门且球经过的每个格点都不能被A\texttt{A}A队球员覆盖。要求使用最少的球员数即传球次数最少若有多个方案则选择总移动距离最短的方案。输入格式输入包含多组测试用例每组一行格式如下四个整数sss、ggg、ppp、nnn其中0s100 s 100s100gs0 g s0gs0ps0 p s0ps0≤n1000 \le n 1000≤n100。随后跟有nnn对整数(x,y)(x, y)(x,y)表示A\texttt{A}A队球员的坐标xxx范围[−s,s][-s, s][−s,s]yyy范围[0,2s][0, 2s][0,2s]。输入以单独的一行0结束。输出格式对于每组测试用例输出一行标识场景序号格式为Scenario X.。若无法进球输出Situation Impossible否则输出Goal with k kicks: (x1,y1)(x2,y2)...(xk1,yk1)其中(xi,yi)(x_i, y_i)(xi​,yi​)i≤ki \le ki≤k表示第iii次踢球时球所在的格点即第iii名球员的位置(xk1,yk1)(x_{k1}, y_{k1})(xk1​,yk1​)是球最终到达的球门线上的点满足yk12sy_{k1} 2syk1​2s且∣xk1∣≤g|x_{k1}| \le g∣xk1​∣≤g。两组输出之间用一个空行隔开。样例输入4 2 1 2 -2 8 1 8 7 2 3 3 0 7 6 10 0 9 9 3 3 1 -5 9 0输出Scenario 1. Situation Impossible Scenario 2. Goal with 3 kicks: (0,0)(-4,0)(-4,14)(-2,14) Scenario 3. Goal with 1 kicks: (0,0)(0,18)题目分析本题的核心是在给定的网格中寻找一条从起点(0,0)(0,0)(0,0)到球门线的最短路径其中路径由若干条水平或垂直的直线段组成每次传球且路径上所有格点均不能被A\texttt{A}A队防守球员覆盖。约束条件是路径的段数即踢球次数不能超过n1n1n1因为可以放置至多nnn名额外球员起点开球者不算在内。在段数最少的前提下要求总曼哈顿距离最短。由于s10s 10s10网格大小不超过20×2020 \times 2020×20状态空间非常小因此可以采用带优先级的搜索算法以段数为主关键字、总距离为次关键字进行广度优先搜索BFS\texttt{BFS}BFS变种。解题思路模型转化将整个球场的坐标整体向右平移sss个单位使得所有格点的xxx坐标落在区间[0,2s][0, 2s][0,2s]内。这样做的好处是可以使用二维数组直接索引每个格点无需偏移常量。平移后的起点变为(s,0)(s, 0)(s,0)球门线变为y2sy 2sy2s且球门范围为∣x−s∣≤g|x - s| \le g∣x−s∣≤g。覆盖判定A\texttt{A}A队球员(a,b)(a, b)(a,b)覆盖所有满足∣x−a∣≤p|x - a| \le p∣x−a∣≤p且∣y−b∣≤p|y - b| \le p∣y−b∣≤p的格点。因此任意格点(x,y)(x, y)(x,y)是否被覆盖只需遍历所有球员检查切比雪夫距离是否不超过ppp即可。由于n≤100n \le 100n≤100且网格很小该检查常数极低。状态表示与搜索定义状态为(x,y,kick,dist)(x, y, \textit{kick}, \textit{dist})(x,y,kick,dist)其中(x,y)(x, y)(x,y)是当前球所在的格点kick\textit{kick}kick是已经执行的踢球次数即已经经过的直线段数dist\textit{dist}dist是累计的曼哈顿移动距离。优先级比较规则首先比较kick\textit{kick}kick较小的优先若相同则比较dist\textit{dist}dist较小的优先。使用优先队列小根堆实现Dijkstra\texttt{Dijkstra}Dijkstra风格的搜索。起点状态为(s,0,0,0)(s, 0, 0, 0)(s,0,0,0)因为尚未执行任何踢球。状态扩展从当前格点出发尝试沿四个方向上、下、左、右直线前进。每次尝试向前走一步到达新的格点若该格点不合法越界或被覆盖则停止该方向的继续前进。否则记录走过的步数step\textit{step}step生成新状态新格点(nx,ny)(nx, ny)(nx,ny)新踢球次数nkkick1\textit{nk} \textit{kick} 1nkkick1新总距离nddiststep\textit{nd} \textit{dist} \textit{step}nddiststep。若nk≤n1\textit{nk} \le n 1nk≤n1因为最多允许n1n1n1次踢球并且该新状态比当前记录的最优状态bestKick[nx][ny]\textit{bestKick}[nx][ny]bestKick[nx][ny]bestDist[nx][ny]\textit{bestDist}[nx][ny]bestDist[nx][ny]更优则更新最优记录记录前驱格点并将新状态入队。目标判定当从优先队列中弹出某个状态时若其y2sy 2sy2s且∣x−s∣≤g|x - s| \le g∣x−s∣≤g则说明球已到达球门线且该状态是当前队列中最优的因为优先级保证了先弹出段数最少、距离最短的状态因此可以立即终止搜索。回溯路径从目标状态开始沿着记录的parent数组回溯到起点即可得到完整的格点序列输出时需将xxx坐标还原减sss。复杂度分析状态数网格格点总数为(2s1)×(2s1)≤19×19361(2s1) \times (2s1) \le 19 \times 19 361(2s1)×(2s1)≤19×19361。每个状态扩展时沿四个方向每个方向最多前进2s2s2s步因此总扩展次数约为O(4×361×2s)≈O(s2)O(4 \times 361 \times 2s) \approx O(s^2)O(4×361×2s)≈O(s2)其中s10s 10s10常数极小。优先队列操作O(log⁡V)O(\log V)O(logV)总时间复杂度可视为O(1)O(1)O(1)量级空间复杂度O(1)O(1)O(1)。代码实现// Grid Soccer// UVa ID: 747// Verdict: Accepted// Submission Date: 2026-07-07// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structstate{intx,y,kick,dist;booloperator(conststateo)const{if(kick!o.kick)returnkicko.kick;returndisto.dist;}};ints,g,p,n;vectorpairint,intplayers;intbestKick[32][32],bestDist[32][32];pairint,intparent[32][32];boolcovered(intx,inty){for(autopl:players){intapl.first,bpl.second;if(abs(x-a)pabs(y-b)p)returntrue;}returnfalse;}boolvalid(intx,inty){returnx0x2*sy0y2*s;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intscenario0;while(cins,s){cingpn;players.clear();for(inti0;in;i){inta,b;cinab;players.push_back({as,b});}for(inti0;i32;i)for(intj0;j32;j){bestKick[i][j]bestDist[i][j]INT_MAX;parent[i][j]{0,0};}priority_queuestate,vectorstate,greaterstatepq;intsxs,sy0;bestKick[sx][sy]bestDist[sx][sy]0;pq.push({s,0,0,0});boolfoundfalse;state target;intdx[4]{1,-1,0,0},dy[4]{0,0,1,-1};while(!pq.empty()){state nowpq.top();pq.pop();intcxnow.x,cynow.y;intcKicknow.kick,cDistnow.dist;if(cKick!bestKick[cx][cy]||cDist!bestDist[cx][cy])continue;if(cy2*sabs(cx-s)g){foundtrue;targetnow;break;}if(cKickn1)continue;for(intd0;d4;d){intnxcx,nycy,step0;while(true){nxdx[d],nydy[d];if(!valid(nx,ny))break;if(covered(nx,ny))break;step;intnkcKick1,ndcDiststep;if(nkn1)break;if(nkbestKick[nx][ny]||(nkbestKick[nx][ny]ndbestDist[nx][ny])){bestKick[nx][ny]nk;bestDist[nx][ny]nd;parent[nx][ny]{cx,cy};pq.push({nx,ny,nk,nd});}}}}if(scenario)cout\n;coutScenario scenario.\n;if(!found)coutSituation Impossible\n;else{vectorpairint,intpath;intcxtarget.x,cytarget.y;while(!(cxscy0)){path.push_back({cx,cy});autopparent[cx][cy];cxp.first,cyp.second;}path.push_back({s,0});reverse(path.begin(),path.end());coutGoal with target.kick kicks: ;for(size_t i0;ipath.size();i)cout(path[i].first-s,path[i].second);cout\n;}}return0;}总结本题的关键在于将实际问题抽象为网格上的最优路径问题并利用网格规模小的特点采用优先队列进行带优先级的搜索。代码中的几个设计亮点值得注意坐标平移将xxx坐标整体加sss使得所有坐标非负便于数组索引简化边界判断。段数优先的搜索通过自定义比较函数保证优先队列总是先弹出踢球次数最少的状态从而首次找到的目标即为最优解。直线扩展每次传球可沿一个方向连续前进多格但每个中间格点都作为候选状态入队保证了不会遗漏可能的转向点。精确的约束控制将踢球次数上限设为n1n1n1完美贴合题目中“至多nnn名额外球员”的定义且代码实现简洁。该解法充分利用了题目的小数据特性以直观的搜索方式解决了实际问题是一道适合练习图论建模和优先队列应用的典型题目。