企业官网建设流程全解析

T1. 夺宝大赛

题目链接：SOJ D1298

夺宝大赛的地图是一个由n × m n×mn×m个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻” 是指两个方格有一条公共边）所花的时间都是1 11个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。

假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。

时间限制：1 s
内存限制：64 MB

• 输入
  输入首先在第一行给出两个正整数m mm和n nn（2 < m , n ≤ 100 2 < m,n ≤ 1002<m,n≤100），随后m mm行，每行给出n nn个数字，表示地图上对应方格的状态：1 11表示方格可通过；0 00表示该方格有障碍物，不可通行；2 22表示该方格是大本营。题目保证只有1 11个大本营。
  接下来是参赛队伍信息。首先在一行中给出正整数k kk（0 < k < m × n 2 0 < k < \frac{m×n}{2}0<k<2m×n​），随后k kk行，第i ii（1 ≤ i ≤ k 1 ≤ i ≤ k1≤i≤k）行给出编号为i ii的参赛队的初始落脚点的坐标，格式为x y。这里规定地图左上角坐标为1 1，右下角坐标为n m，其中n nn为列数，m mm为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。
• 输出
  在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以1 11个空格分隔，行首尾不得有多余空格。
  若没有队伍能获胜，则在一行中输出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

• 样例输入 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.

• 提示
  样例1 11说明：七支队伍到达大本营的时间顺次为：7 77、不可能、5 55、3 33、3 33、5 55、6 66，其中队伍4 44和5 55火拼了，队伍3 33和6 66火拼了，队伍7 77比队伍1 11早到，所以获胜。

思路分析

此题考察B F S \tt BFSBFS，属于基础题。

不难想到从每个参赛队所在点出发，做一次B F S \tt BFSBFS求出到达大本营的最短时间，然后从小到大依次检测每一个时刻到达大本营的参赛队伍数量，如果某时刻只有一个队伍到达，那么该参赛队伍就是最终赢家。该方法需要进行k kk次B F S \tt BFSBFS。

如果从大本营出发，则只需要一次B F S \tt BFSBFS就可以求出所有参赛队伍到达大本营的最短时间，并且可以在B F S \tt BFSBFS的过程中检测获胜队伍。具体来说，在遍历过程中统计当前层遇到的参赛队伍数量，如果某层仅出现一支队伍，该队伍即为获胜者。

代码实现过程中的细节参考示例代码。

/* * Name: T1.cpp * Problem: 夺宝大赛 * Author: Teacher Gao. * Date&Time: 2026/04/23 19:12 */#include<bits/stdc++.h>usingnamespacestd;constintN=105;constintdx[]={0,0,-1,1},dy[]={-1,1,0,0};intn,m,sx,sy;intg[N][N];structnode{intx,y,cnt;};voidBFS(){queue<node>Q;Q.push({sx,sy,0});g[sx][sy]=0;while(!Q.empty()){// 每次取出同一层的所有点，即 cnt 相同intt=Q.size(),cntt=0,res,resc;while(t--){node tmp=Q.front();Q.pop();for(inti=0;i<4;i++){intxx=tmp.x+dx[i];intyy=tmp.y+dy[i];if(xx<1||xx>m||yy<1||yy>n||!g[xx][yy])continue;// 大于 1 说明是队伍，统计同一层内的队伍if(g[xx][yy]>1){cntt++;res=g[xx][yy],resc=tmp.cnt+1;}g[xx][yy]=0;Q.push({xx,yy,tmp.cnt+1});}}// 同一层只有一个队伍时结束if(cntt==1){cout<<res-10<<" "<<resc;return;}}cout<<"No winner.";}intmain(){cin>>m>>n;for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){cin>>g[i][j];if(g[i][j]==2)sx=i,sy=j;}}intk,x,y;cin>>k;for(inti=1;i<=k;i++){cin>>y>>x;// 注意这里输入是列在前面g[x][y]=10+i;// 将参赛队和其他点区别开}BFS();return0;}

T2. 清点代码库

题目链接：SOJ D1299

很久之前新浪微博有人发过：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了…”

这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在int范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

时间限制：1 s
内存限制：256 MB

• 输入
  输入在第一行中给出2 22个正整数，依次为N NN（≤ 10 4 ≤ 10^4≤104）和M MM（≤ 10 2 ≤ 10^2≤102），对应功能模块的个数和系列测试输入的个数。
  随后N NN行，每行给出一个功能模块的M MM个对应输出，数字间以空格分隔。
• 输出
  首先在第一行输出不同功能的个数K KK。
  随后K KK行，每行给出具有这个功能的模块的个数，以及这个功能的对应输出。数字间以1 11个空格分隔，行首尾不得有多余空格。输出首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序给出。
  注：所谓数列{ A 1 , … , A M } \{ A_1, …, A_M \}{A1​,…,AM​}比{ B 1 , … , B M } \{ B_1, …, B_M \}{B1​,…,BM​}大，是指存在