Teacher 解题报告 | 宁心勉学，慎思笃行

题目描述

老师坐在机房的教师机旁写程序，现在他想到出去接杯水。但是同学们在下面做题，他不想打扰同学们。

可以把机房理解为一个N*M的方阵，老师或者一个同学占一个方格，当然有的方格是空着的，没有人。

机房的出口也占一个方格，每一步都可以从一个方格走到和它的边或者顶点连接的8个方格（边界处除外），为了不打扰同学们，他希望自己的路线上经过的格子离其他人的最近距离最远。

对于两个点（X1,Y1）(X2,Y2)，他们的距离为相互之间按照上面的规则走到的最少步数。

输入：第一行，两个整数N,M（N,M<=1000）以下N行，每行M个字符，字符只可能是‘.’‘D’‘@’‘$’中的一个字符是‘.’，表示此处是空地字符是‘D’，表示此处有一个同学字符是‘@’，表示老师现在的位置字符是‘$’，表示机房的出口

输出：一个整数，表示老师路线上经过的格子离其他人的最近距离最远时的最近距离。样例输入1: 7 5 ….$ ….. ….. D…D ….. ….. @….

样例输出1： 2 样例输入2： 7 5 ….$ ….. ….. DDDDD ….. ….. @…. 样例输出2： 0

思路分析

这个题是搜索题目。由于时间限制是5s，所以让人感觉到应该是搜索……但搜索的时候有一些优化的地方。

第一，我们需要知道每个点到学生的最短距离。但我们无需一个一个学生的去求，再求最小值，而可以用宽搜去直接松弛所有学生，只保留最短距离即可，那么时间复杂度就减少到了O(n*n)。然后再搜索，看对于某个到学生的最短距离，能否找出一条路径让老师走。如果可以走，就二分搜索是否有更长的最短距离可以找出一条路径；否则就搜索更短的那个二分区间。

总体时间复杂度为O(n*n)。最长用时，第九个点1.56s，远小于规定时间5s。

//By Ceeji 
//Date: 2009-4-7 
//HAOI test 6 - Problem 3: Teacher 
//Type: DP 
//State: Accepted 
Program teacher; 
Const 
   maxnm=1000; 
   inf='teacher.in'; 
   ouf='teacher.out'; 
   yd:array[1..8,1..2]of integer=((-1,0),(1,0),(0,1),(0,-1),(-1,-1),(1,1),(-1,1),(1,-1)); 
Type 
   node=record 
          x,y,d:integer; 
        end; 
   node2=record 
          x,y:integer; 
        end; 

Var 
   zt:array[1..maxnm*maxnm]of node; 
   l:array[1..maxnm,1..maxnm]of integer; 
   sx,sy,ex,ey,n,m,ztn,kzs,zs,maxl,minl,ans:longint; 
   zt2:array[1..maxnm*maxnm]of node2; 
   b:array[1..maxnm,1..maxnm]of boolean; 
Procedure init; 
var i,j:longint; 
    c:char; 
begin 
   assign(input,inf);   reset(input); 
   assign(output,ouf);  rewrite(output); 
   fillchar(zt,sizeof(zt),0); 
   readln(n,m); 
   ztn:=0; 
   for i:=1 to n do 
     for j:=1 to m do 
       l[i,j]:=-1; 
   for i:=1 to n do 
   begin 
      for j:=1 to m do 
      begin 
         read(c); 
         if c='@' then begin sx:=i; sy:=j; end; 
         if c='D' then begin 
           inc(ztn); 
           zt[ztn].x:=i; 
           zt[ztn].y:=j; 
           zt[ztn].d:=0; 
           l[i,j]:=0; 
         end; 
         if c='$' then begin ex:=i; ey:=j; end; 
      end; 
      readln; 
   end; 
   close(input); 
   zs:=m*n; 
end; 

Procedure bfs; 
var i,j,k,nx,ny:longint; 
begin 
    i:=1; j:=ztn+1; 
    kzs:=ztn; 
    repeat 
        for k:=1 to 8 do 
        begin 
            nx:=zt[i].x+yd[k,1]; ny:=zt[i].y+yd[k,2]; 
            if (nx>=1)and(nx<=m)and(ny>=1)and(ny<=n) then 
            begin 
               if (l[nx,ny]=-1)or(l[nx,ny]>zt[i].d+1) then 
               begin 
                  l[nx,ny]:=zt[i].d+1; 
                  zt[j].x:=nx; 
                  zt[j].y:=ny; 
                  zt[j].d:=zt[i].d+1; 
                  inc(j); 
               end; 
            end; 
        end; 
        inc(i); 
    until i>=j; 
    maxl:=0; 
    for i:=1 to n do 
      for j:=1 to m do 
      begin 
         if l[i,j]>maxl then maxl:=l[i,j]; 
      end; 
end; 

Function tryit(lmin,lmax:integer):boolean; 
var ll,k,nx,ny:integer; 
    i,j:longint; 
begin 
   ll:=(lmin+lmax)>>1; 
   zt2[1].x:=sx; zt2[1].y:=sy; 
   i:=1; j:=2; 
   fillchar(b,sizeof(b),0); 
   b[sx,sy]:=true; 
   repeat 
      for k:=1 to 8 do 
      begin 
         nx:=zt2[i].x+yd[k,1]; ny:=zt2[i].y+yd[k,2]; 
         if (nx>=1)and(nx<=m)and(ny>=1)and(ny<=n)and(l[nx,ny]>=ll) then 
         begin 
            if (nx=ex)and(ny=ey) then 
            begin 
              exit(true); 
            end; 
            if b[nx,ny]=false then 
            begin 
               b[nx,ny]:=true; 
               zt2[j].x:=nx; 
               zt2[j].y:=ny; 
               inc(j); 
            end; 
         end; 
      end; 
      inc(i); 
   until i>=j; 
   exit(false); 
end; 

begin 
   init; 
   bfs; 
   minl:=0; ans:=0; 
   while true do 
   begin 
      if tryit(minl,maxl)=false then maxl:=(minl+maxl)>>1-1 
      else begin ans:=(minl+maxl)>>1; minl:=(minl+maxl)>>1+1; end; 
      if minl>maxl then break; 
   end; 
   writeln(ans); 
   close(output); 
end.

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。

猜你喜欢