记录编号	14688	评测结果	AAAAAAAAAAA
题目名称	[USACO Oct09] 乳草的入侵	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	0.015 s
提交时间	2009-11-03 12:48:42	内存使用	0.31 MiB

program xmz;
var
f1,f2:text;
x:array[0..101,0..101]of char;
f:array[0..101,0..101]of longint;
dx,dy:array[1..20000]of longint;

h,m,n,x1,y1,a,b,s:longint;
begin
 assign(f1,'milkweed.in');assign(f2,'milkweed.out');
 reset(f1);rewrite(f2);
 read(f1,m,n);
 readln(f1,dx[1],dy[1]);
 h:=1;
 for a:=n downto 1 do
  begin
   for b:=1 to m do
    read(f1,x[b,a]);
   readln(f1);
  end;
 for a:=1 to n do
  for b:=1 to m do
   f[b,a]:=99999999;
 f[dx[1],dy[1]]:=0;
 a:=0;
 repeat
  inc(a);
  if (dx[a]+1>0)and(dx[a]+1<=m)and(dy[a]>0)and(dy[a]<=n)and(f[dx[a]+1,dy[a]]>f[dx[a],dy[a]]+1)and(x[dx[a]+1,dy[a]]<>'*') then
  begin inc(h);dx[h]:=dx[a]+1;dy[h]:=dy[a];f[dx[a]+1,dy[a]]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]-1>0)and(dx[a]-1<=m)and(dy[a]>0)and(dy[a]<=n)and(f[dx[a]-1,dy[a]]>f[dx[a],dy[a]]+1)and(x[dx[a]-1,dy[a]]<>'*') then
  begin inc(h);dx[h]:=dx[a]-1;dy[h]:=dy[a];f[dx[a]-1,dy[a]]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]>0)and(dx[a]<=m)and(dy[a]+1>0)and(dy[a]+1<=n)and(f[dx[a],dy[a]+1]>f[dx[a],dy[a]]+1)and(x[dx[a],dy[a]+1]<>'*') then
  begin inc(h);dx[h]:=dx[a];dy[h]:=dy[a]+1;f[dx[a],dy[a]+1]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]>0)and(dx[a]<=m)and(dy[a]-1>0)and(dy[a]-1<=n)and(f[dx[a],dy[a]-1]>f[dx[a],dy[a]]+1)and(x[dx[a],dy[a]-1]<>'*') then
  begin inc(h);dx[h]:=dx[a];dy[h]:=dy[a]-1;f[dx[a],dy[a]-1]:=f[dx[a],dy[a]]+1;end;

  if (dx[a]+1>0)and(dx[a]+1<=m)and(dy[a]-1>0)and(dy[a]-1<=n)and(f[dx[a]+1,dy[a]-1]>f[dx[a],dy[a]]+1)and(x[dx[a]+1,dy[a]-1]<>'*') then
  begin inc(h);dx[h]:=dx[a]+1;dy[h]:=dy[a]-1;f[dx[a]+1,dy[a]-1]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]-1>0)and(dx[a]-1<=m)and(dy[a]-1>0)and(dy[a]-1<=n)and(f[dx[a]-1,dy[a]-1]>f[dx[a],dy[a]]+1)and(x[dx[a]-1,dy[a]-1]<>'*') then
  begin inc(h);dx[h]:=dx[a]-1;dy[h]:=dy[a]-1;f[dx[a]-1,dy[a]-1]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]+1>0)and(dx[a]+1<=m)and(dy[a]+1>0)and(dy[a]+1<=n)and(f[dx[a]+1,dy[a]+1]>f[dx[a],dy[a]]+1)and(x[dx[a]+1,dy[a]+1]<>'*') then
  begin inc(h);dx[h]:=dx[a]+1;dy[h]:=dy[a]+1;f[dx[a]+1,dy[a]+1]:=f[dx[a],dy[a]]+1;end;
  if (dx[a]-1>0)and(dx[a]-1<=m)and(dy[a]+1>0)and(dy[a]+1<=n)and(f[dx[a]-1,dy[a]+1]>f[dx[a],dy[a]]+1)and(x[dx[a]-1,dy[a]+1]<>'*') then
  begin inc(h);dx[h]:=dx[a]-1;dy[h]:=dy[a]+1;f[dx[a]-1,dy[a]+1]:=f[dx[a],dy[a]]+1;end;
 until a=h;

 for a:=1 to n do
  for b:=1 to m do
   if x[b,a]<>'*' then
   if f[b,a]=99999999 then s:=-1
   else if (s<f[b,a])and(s<>-1) then s:=f[b,a];
   writeln(f2,s);
 close(f1);close(f2);
end.