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.

猜你喜歡