回 帖 发 新 帖 刷新版面

主题:[讨论]高手快来“单挑女飞贼”啊!

描述 Description   
   在一个夜黑风高,伸手不见五指的深夜,睡梦中的林月如突然听到房外一阵躁动。她出去一看,发现一个女飞贼抢了一个古董商的包袱。
  "站住!"
  "那你为什么不来追我?"
  "因为程序设计,在李大哥来之前,我不能追你。"
  "那李逍遥为什么不来呢?"
  "大概程序出bug了吧"
……………………………………………… 
终于,在等了一个又一个时辰后,林月如终于忍不住了,开始向女飞贼发起进攻。
"喂!你为什么可以动???"
"这大概也是一个bug吧!"
"不公平啊!"
"废话少说。"

已知林月如和女飞贼站在一个矩阵中,矩阵中有某些障碍物不可穿越。月如使出的铜钱镖可攻击8个方向,但不可穿越障碍物(可视为不能穿墙的重狙)。每个单位时间,月如可向上下左右4个方向移动一格,攻击不浪费时间。当然,月如想尽快结束这场无聊的战斗,所以她想在最短的时间内消灭女飞贼。
    
输入格式 Input Format  
   第一行为2个数N,M表示矩阵的规模(N为高,M为宽)。
接下来是N*M的矩阵,O表示空地,X表示障碍物。
下面是若干行数据,每行为一对数据,分别是女飞贼的位置和林月如的位置,显然她们都不可能在障碍物上。
以"0 0 0 0"为输入结束标志。
 
输出格式 Output Format  
   每一组数据输出一行,仅一个整数,表示能消灭掉女飞贼的最短时间。
 显然若能直接打到女飞贼,则时间为0。
 若无法消灭,则输出"Impossible!"。(不含引号)
  
样例输入 Sample Input   
 3 4
 OXXO
 XXOO
 XOOO
 3 2 2 4
 3 3 1 1
 0 0 0 0
 
样例输出 Sample Output   
  1
  Impossible!

时间限制 Time Limitation  
  1s
 
注释 Hint  
 对于30%的数据,有N*M<=100
 对于50%的数据,有N*M<=400
 对于100%的数据,有N*M<=20000
 对于100%的数据,测试数据组数不超过20组

回复列表 (共5个回复)

沙发

看看我的程序:
  //有些地方有错!!  大家帮我找找!谢谢大家啦!![em12]
const dx:array[1..8] of shortint=(1,-1,0,0,1,1,-1,-1);
      dy:array[1..8] of shortint=(0,0,1,-1,1,-1,1,-1);
var i,j,t,x1,x2,y1,y2,n,m,h,cl,op:integer;
    s,att,visited:array[0..201,0..201] of boolean;
    x,y:array[0..20000] of integer;
    c:char;
procedure deal(x,y:integer);
 var a,b,k:integer;
 begin
  for k:=1 to 8 do
   begin
    a:=x+dx[k];b:=y+dy[k];
    while (a>0)and(b>0)and(a<=n)and(b<=m)and(s[a,b]=false) do
     begin
      att[a,b]:=true;
      a:=a+dx[k];b:=b+dy[k];
     end;
   end;
 end;
procedure expand;
 var a,b,k:integer;
 begin
  x[1]:=x2;y[1]:=y2;
  if att[x2,y2] then begin writeln('0'); exit; end;
  repeat
   inc(cl);inc(t);
   for k:=1 to 4 do
    begin
     a:=x[cl]+dx[k];b:=y[cl]+dy[k];
     if (a>0)and(b>0)and(a<=n)and(b<=m)and(s[a,b]=false)and(visited[a,b]=false) then
      begin
       inc(op);
       visited[a,b]:=true;
       x[op]:=a;y[op]:=b;
       if att[a,b] then begin h:=1; break; end;
      end;
    end;
   if h=1 then break;
  until cl>op;
  if h=0 then writeln('Impossible!')
         else writeln(t);
 end;
begin
 readln(n,m);
 for i:=1 to n do
  begin
   for j:=1 to m do
    begin
     read(c);
     if c='X' then s[i,j]:=true
              else s[i,j]:=false;
    end;
   readln;
  end;
 repeat
   readln(x1,y1,x2,y2);
   fillchar(att,sizeof(att),false);
   fillchar(visited,sizeof(visited),false);
   fillchar(x,sizeof(x),0);
   fillchar(y,sizeof(y),0);
   h:=0;t:=0;cl:=0;op:=1;
   deal(x1,y1);
   if x1<>0 then expand;
  until x1=0;
end.

板凳

林月如要是会乾坤一掷就不用这么麻烦了..^_^

3 楼

那女飞贼会移动吗?

4 楼

[color=FF0000][size=5]Notice:[/size][/color]:[size=4]女飞贼不移动![/size]

5 楼

那就简单,直接用深搜搜索出一条可以打到女飞贼的最短路径

我来回复

您尚未登录,请登录后再回复。点此登录或注册