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.
本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。