p1340.pas

来自「www.vijos.cn上一些习题的参考源码」· PAS 代码 · 共 120 行

program p1340(input,output);
{$M 16777216}
label 99;
const
    MAXN=30;
    MAXM=30;
    dx:array[1..4] of integer=(-1,1,0,0);
    dy:array[1..4] of integer=(0,0,-1,1);
var
    map:array[0..MAXN+1,0..MAXM+1] of char;
    t,m,n:integer;
    i,j:integer;
    f,cost:array[1..MAXN,1..MAXM] of integer;
    sx,sy,ex,ey:integer;
    visited:array[1..MAXN,1..MAXM] of boolean;
    k:integer;

function search(x,y:integer):integer;
var
    i,d:integer;
    nx,ny:integer;

function min(a,b:integer):integer;
begin
    if a<b then min:=a
    else min:=b;
end;

begin
    if (f[x,y]<>maxint) then exit(f[x,y]);
    if map[x,y]='m' then exit(0);
    f[x,y]:=9999;
    for i:=1 to 4 do begin
        nx:=x+dx[i]; ny:=y+dy[i];
        if (map[nx,ny]<>'o') and not visited[nx,ny] then begin
            visited[nx,ny]:=true;
            {inc(k);
            if k>19999 then goto 99;
            writeln(nx,' ',ny);}
            if search(nx,ny)+cost[nx,ny]<f[x,y] then
               f[x,y]:=search(nx,ny)+cost[nx,ny];
            visited[nx,ny]:=false;
        end;
    end;
    exit(f[x,y]);
end;

function search1(x,y,k:integer):integer;
begin
    if k<f[x,y] then begin
        f[x,y]:=k;


end;


{function search(x,y:integer):integer;
var
    nx,ny:integer;
    b,tmp:integer;
    i:integer;
begin
    if (map[x,y]='m') then begin
        search:=0; exit; end;
    if f[x,y]<>maxint then begin search:=f[x,y]; exit; end;
    if not visited[x,y] then begin
    b:=9999;
    for i:=1 to 4 do begin
        nx:=x+dx[i]; ny:=y+dy[i];
        if (map[nx,ny]<>'o') and not visited[nx,ny] then begin
            visited[nx,ny]:=true;
            case map[nx,ny] of
                'm','.':begin  tmp:=search(nx,ny)+1; end;
                '#':begin  tmp:=search(nx,ny)+2; end;

            end;
            visited[nx,ny]:=false;
            if tmp<b then b:=tmp;
        end;
    end;
    f[x,y]:=b;
    search:=f[x,y];
    end;
end;}

begin
    assign(input,'e:\tmp\vijos\p1340.in'); reset(input);
    assign(output,'e:\tmp\vijos\p1340.out'); rewrite(output);
    readln(t);
    readln(m);
    readln(n);

    fillchar(cost,sizeof(cost),0);
    fillchar(visited,sizeof(visited),false);
    for i:=1 to n do begin
        for j:=1 to m do begin
            read(map[i,j]);
            if map[i,j]='s' then begin sx:=i; sy:=j; visited[i,j]:=true; end;
            if map[i,j]='m' then begin ex:=i; ey:=j; cost[i,j]:=0; end;
            if map[i,j]='.' then cost[i,j]:=1;
            if map[i,j]='#' then cost[i,j]:=1;
            f[i,j]:=maxint;
        end;
        readln;
    end;

    for i:=0 to n+1 do begin map[i,0]:='o'; map[i,m+1]:='o'; end;
    for j:=1 to m do begin map[0,j]:='o'; map[n+1,j]:='o'; end;

    if search(sx,sy)<t then writeln(f[sx,sy])
    else writeln('55555');
99:
    for i:=1 to n do begin
        for j:=1 to m do write(f[i,j]:6);
        writeln;
    end;
    close(input);
    close(output);
end.