CUTRECT - Cắt hình chữ nhật

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  MAXN=411;
  oo=1000111000111;

var
  i,j,m,n,u,v:longint;
  hpos,d,cot,hang:array[1..411,1..411] of int64;
  res:int64;

  hu,hv:array[1..411*411] of longint;
  hsize:longint;

procedure swap(var a,b:longint); inline;
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure swapi(var a,b:int64); inline;
    var
      tmp:int64;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure swapH(a,b:longint); inline;
    begin
      swapi(hpos[hu[a],hv[a]], hpos[hu[b],hv[b]]);
      swap(hu[a],hu[b]);
      swap(hv[a],hv[b]);
    end;

function lower(a,b:longint):boolean; inline;
    begin
      exit( d[hu[a],hv[a]] < d[hu[b],hv[b]]);
    end;

procedure down(i:longint); inline;
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and lower(j+1,j) then inc(j);
          if lower(j,i) then
            begin
              swapH(i,j);
              i:=j; j:=i shl 1;
            end
          else exit;
        end;
    end;

procedure up(i:longint); inline;
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and lower(i,j) do
        begin
          swapH(i,j);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u,v:longint); inline;
    begin
      inc(hsize);
      hu[hsize]:=u; hv[hsize]:=v;
      hpos[u,v]:=hsize;
      up(hsize);
    end;

procedure pop(var u,v:longint); inline;
    begin
      u:=hu[1]; v:=hv[1];
      swap(hu[1],hu[hsize]);
      swap(hv[1],hv[hsize]);
      hpos[hu[1],hv[1]]:=1;
      dec(hsize);
      down(1);
    end;

procedure update(u,v:longint; k:int64);
    begin
      if d[u,v]>k then
        begin
          d[u,v]:=k;
          if hpos[u,v]=0 then push(u,v)
          else up(hpos[u,v]);
        end;
    end;

procedure ijk;
    begin
      while (hsize>0) do
        begin
          pop(u,v);
          if ((v=1) and (u>=2)) or ((u=m+1) and (v<=n)) then
            begin
              res:=min(res,d[u,v]);
              break;
            end;
          if (u>=2) and (u<=m) and (v>=2) and (v<=n+1) then update(u,v-1,d[u,v]+hang[u-1,v-1]);
          if (u>=2) and (u<=m) and (v>=1) and (v<=n) then update(u,v+1,d[u,v]+hang[u-1,v]);
          if (u>=2) and (u<=m) and (v>=2) and (v<=n) then update(u-1,v,d[u,v]+cot[u-1,v-1]);
          if (u>=1) and (u<=m) and (v>=2) and (v<=n) then update(u+1,v,d[u,v]+cot[u,v-1]);
        end;

    end;

begin
  for i:=1 to 411 do
  for j:=1 to 411 do
    begin
      d[i,j]:=oo;
      hang[i,j]:=oo;
      cot[i,j]:=oo;
    end;

  read(m,n);
  for i:=1 to m do
    for j:=1 to n-1 do
      read(cot[i,j]);

  for i:=1 to m-1 do
    for j:=1 to n do
      read(hang[i,j]);


  for i:=1 to m+1 do
    begin
      d[i,n+1]:=0;
      push(i,n+1);
    end;

  res:=oo;
  ijk;

  for i:=1 to 411 do
  for j:=1 to 411 do
    d[i,j]:=oo;

  fillchar(hpos,sizeof(hpos),0); hsize:=0;
  for i:=1 to n+1 do
    begin
      d[1,i]:=0;
      push(1,i);
    end;

  ijk;

  if res=oo then res:=-1;
  writeln(res);
end.

Download