题目描述

一场重要的足球比赛即将在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个方格的网格，球门位于Y=2sY = 2sY=2s直线上，占据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，其中0<s<100 < s < 100<s<10，0<g<s0 < g < s0<g<s，0<p<s0 < p < s0<p<s，0≤n<1000 \le n < 1000≤n<100。
• 随后跟有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)...(xk+1,yk+1)，其中(xi,yi)(x_i, y_i)(xi​,yi​)（i≤ki \le ki≤k）表示第iii次踢球时球所在的格点（即第iii名球员的位置），(xk+1,yk+1)(x_{k+1}, y_{k+1})(xk+1​,yk+1​)是球最终到达的球门线上的点，满足yk+1=2sy_{k+1} = 2syk+1​=2s且∣xk+1∣≤g|x_{k+1}| \le g∣xk+1​∣≤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队防守球员覆盖。约束条件是路径的段数（即踢球次数）不能超过n+1n+1n+1（因为可以放置至多nnn名额外球员，起点开球者不算在内）。在段数最少的前提下，要求总曼哈顿距离最短。

由于s<10s < 10s<10，网格大小不超过20×2020 \times 2020×20，状态空间非常小，因此可以采用带优先级的搜索算法，以段数为主关键字、总距离为次关键字进行广度优先搜索（BFS\texttt{BFS}BFS）变种。

解题思路

模型转化

将整个球场的坐标整体向右平移sss个单位，使得所有格点的xxx坐标落在区间[0,2s][0, 2s][0,2s]内。这样做的好处是可以使用二维数组直接索引每个格点，无需偏移常量。平移后的起点变为(s,0)(s, 0)(s,0)，球门线变为y=2sy = 2sy=2s，且球门范围为∣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)，新踢球次数nk=kick+1\textit{nk} = \textit{kick} + 1nk=kick+1，新总距离nd=dist+step\textit{nd} = \textit{dist} + \textit{step}nd=dist+step。

若nk≤n+1\textit{nk} \le n + 1nk≤n+1（因为最多允许n+1n+1n+1次踢球），并且该新状态比当前记录的最优状态（bestKick[nx][ny]\textit{bestKick}[nx][ny]bestKick[nx][ny]，bestDist[nx][ny]\textit{bestDist}[nx][ny]bestDist[nx][ny]）更优，则更新最优记录，记录前驱格点，并将新状态入队。

目标判定

当从优先队列中弹出某个状态时，若其y=2sy = 2sy=2s且∣x−s∣≤g|x - s| \le g∣x−s∣≤g，则说明球已到达球门线，且该状态是当前队列中最优的（因为优先级保证了先弹出段数最少、距离最短的状态），因此可以立即终止搜索。

回溯路径

从目标状态开始，沿着记录的parent数组回溯到起点，即可得到完整的格点序列，输出时需将xxx坐标还原（减sss）。

复杂度分析

• 状态数：网格格点总数为(2s+1)×(2s+1)≤19×19=361(2s+1) \times (2s+1) \le 19 \times 19 = 361(2s+1)×(2s+1)≤19×19=361。
• 每个状态扩展时沿四个方向，每个方向最多前进2s2s2s步，因此总扩展次数约为O(4×361×2s)≈O(s2)O(4 \times 361 \times 2s) \approx O(s^2)O(4×361×2s)≈O(s2)，其中s<10s < 10s<10，常数极小。
• 优先队列操作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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structstate{intx,y,kick,dist;booloperator>(conststate&o)const{if(kick!=o.kick)returnkick>o.kick;returndist>o.dist;}};ints,g,p,n;vector<pair<int,int>>players;intbestKick[32][32],bestDist[32][32];pair<int,int>parent[32][32];boolcovered(intx,inty){for(auto&pl:players){inta=pl.first,b=pl.second;if(abs(x-a)<=p&&abs(y-b)<=p)returntrue;}returnfalse;}boolvalid(intx,inty){returnx>=0&&x<=2*s&&y>=0&&y<=2*s;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intscenario=0;while(cin>>s,s){cin>>g>>p>>n;players.clear();for(inti=0;i<n;++i){inta,b;cin>>a>>b;players.push_back({a+s,b});}for(inti=0;i<32;i++)for(intj=0;j<32;j++){bestKick[i][j]=bestDist[i][j]=INT_MAX;parent[i][j]={0,0};}priority_queue<state,vector<state>,greater<state>>pq;intsx=s,sy=0;bestKick[sx][sy]=bestDist[sx][sy]=0;pq.push({s,0,0,0});boolfound=false;state target;intdx[4]={1,-1,0,0},dy[4]={0,0,1,-1};while(!pq.empty()){state now=pq.top();pq.pop();intcx=now.x,cy=now.y;intcKick=now.kick,cDist=now.dist;if(cKick!=bestKick[cx][cy]||cDist!=bestDist[cx][cy])continue;if(cy==2*s&&abs(cx-s)<=g){found=true;target=now;break;}if(cKick==n+1)continue;for(intd=0;d<4;++d){intnx=cx,ny=cy,step=0;while(true){nx+=dx[d],ny+=dy[d];if(!valid(nx,ny))break;if(covered(nx,ny))break;step++;intnk=cKick+1,nd=cDist+step;if(nk>n+1)break;if(nk<bestKick[nx][ny]||(nk==bestKick[nx][ny]&&nd<bestDist[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";cout<<"Scenario "<<++scenario<<".\n";if(!found)cout<<"Situation Impossible\n";else{vector<pair<int,int>>path;intcx=target.x,cy=target.y;while(!(cx==s&&cy==0)){path.push_back({cx,cy});autop=parent[cx][cy];cx=p.first,cy=p.second;}path.push_back({s,0});reverse(path.begin(),path.end());cout<<"Goal with "<<target.kick<<" kicks: ";for(size_t i=0;i<path.size();++i)cout<<"("<<path[i].first-s<<","<<path[i].second<<")";cout<<"\n";}}return0;}

总结

本题的关键在于将实际问题抽象为网格上的最优路径问题，并利用网格规模小的特点，采用优先队列进行带优先级的搜索。代码中的几个设计亮点值得注意：

• 坐标平移：将xxx坐标整体加sss，使得所有坐标非负，便于数组索引，简化边界判断。
• 段数优先的搜索：通过自定义比较函数，保证优先队列总是先弹出踢球次数最少的状态，从而首次找到的目标即为最优解。
• 直线扩展：每次传球可沿一个方向连续前进多格，但每个中间格点都作为候选状态入队，保证了不会遗漏可能的转向点。
• 精确的约束控制：将踢球次数上限设为n+1n+1n+1，完美贴合题目中“至多nnn名额外球员”的定义，且代码实现简洁。

该解法充分利用了题目的小数据特性，以直观的搜索方式解决了实际问题，是一道适合练习图论建模和优先队列应用的典型题目。