PTA L3-037 夺宝大赛(C++ 含代码解释)
夺宝大赛的地图是一个由 n×m 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。
假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。
输入格式：
输入首先在第一行给出两个正整数 m 和 n（2<m,n≤100），随后 m 行，每行给出 n 个数字，表示地图上对应方格的状态：1 表示方格可通过；0 表示该方格有障碍物，不可通行；2 表示该方格是大本营。题目保证只有 1 个大本营。
接下来是参赛队伍信息。首先在一行中给出正整数 k（0<k<m×n/2），随后 k 行，第 i（1≤i≤k）行给出编号为 i 的参赛队的初始落脚点的坐标，格式为x y。这里规定地图左上角坐标为1 1，右下角坐标为n m，其中n为列数，m为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。
输出格式：
在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出No winner.
输入样例 1：
5 7 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 2 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 7 1 5 7 1 1 1 5 5 3 1 3 5 1 4输出样例 1：
7 6样例 1 说明：
七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。
输入样例 2：
5 7 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 2 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 7 7 5 1 3 7 1 1 1 5 5 3 1 3 5输出样例 2：
No winner.思路：
这是一道经典的BFS逆向搜索问题，如果使用惯性思维，对于每个点都计算一次到终点的距离，很明显会超时。因此，对于此类问题，运用“洪水填充”的思维，从终点出发并向四周发散，只需要一次BFS，便能自动确定所有起点到终点的距离。我在这里使用数组d记录距离，d[nx]=d[x]+1。需要注意的是，这道题说的是n*m的图，但输出的是m和n,要记得换一下输入顺序！还有一个恶心的点，我第一次提交的时候N开的是100（因为题目说的是m,n<=100），但提交了以后显示两个段错误，后来把N改成1e4，就能AC了。
AC代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e4; //记得N开大一点,二维数组开到1e5以内一般都没事 int mp[N][N]; //存图 int d[N][N],vis[N][N]; //距离数组 判重数组 struct st //结构体记录每队耗时 { int id,x,y; int cnt; }stu[N]; struct node { int x,y; }; int compare(st a,st b) { return a.cnt<b.cnt; } int dx[4]={-1,0,1,0}; //探照灯 代表左下右上四个方向 int dy[4]={0,1,0,-1}; queue<node>q; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin>>n>>m; int xx,yy; //记录终点坐标 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>mp[i][j]; if(mp[i][j]==2) { xx=i,yy=j; } } } int k; cin>>k; for(int i=1;i<=k;i++) { int x,y; cin>>y>>x; //注意这里输出顺序要换一下 stu[i]={i,x,y}; //记录每个队的起点坐标 } q.push({xx,yy}); //从终点开始向四周发散 vis[xx][yy]=1; while(q.size()) { auto t=q.front(); q.pop(); int x=t.x,y=t.y; for(int i=0;i<4;i++) { int nx=x+dx[i]; //更新位置 int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||mp[nx][ny]==0) continue; vis[nx][ny]=1; d[nx][ny]=d[x][y]+1; //新的位置距离=旧位置距离+1 q.push({nx,ny}); //入队 } } for(int i=1;i<=k;i++) { int x=stu[i].x; int y=stu[i].y; stu[i].cnt=d[x][y]; //存储每个队伍到终点的距离 } sort(stu+1,stu+1+k,compare); //按队伍耗时从小到大排序 int i=1; while(1) { if(stu[i].cnt==0) //耗时为0说明该队不可达，直接跳过 { i++; } int cnt=stu[i].cnt; int id=stu[i].id; int j; for(j=i+1;j<=k;j++) //把会火并的队伍剔除 { if(stu[j].cnt==cnt) continue; else break; } if(j==i+1) //对于第一支不会火并的队伍，输出结果 { if(stu[i].cnt!=0) cout<<stu[i].id<<" "<<stu[i].cnt; else cout<<"No winner.";//否则，数组越界，那么距离必然为0，此时没有winner return 0; } else i=j; } return 0; }