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

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      dx:array[1..4] of longint=(-1,0,1,0);
      dy:array[1..4] of longint=(0,1,0,-1);
      maxn=440;
      oo:int64=1000000000;
var m,n,sd,nh:longint;
    doc,ngang:array[0..maxn,0..maxn] of longint;
    pos,cur,h,p:array[1..maxn*maxn] of longint;
    d:array[1..maxn*maxn] of int64;
    a,c:array[1..maxn*maxn*4+maxn*4] of longint;
    stt:array[0..maxn,0..maxn] of longint;
    free:array[1..maxn*maxn] of boolean;
    re:int64;

procedure rf;
var i,j:longint;
begin
     read(m,n);
     if (m=1) and (n=1) then 
     begin
          writeln(-1); halt;
     end;
     for i:=1 to m do
         for j:=1 to n-1 do
             read(doc[i,j]);
     for i:=1 to m-1 do
         for j:=1 to n do
             read(ngang[i,j]);
end;

function calc(i,j,ii,jj:longint):longint;
begin
     if i=ii then
     begin
          if j>jj then calc:=ngang[i,j]
          else calc:=ngang[i,jj];
     end
     else
     begin
          if i>ii then calc:=doc[i,j]
          else calc:=doc[ii,j];
     end;
end;

procedure init;
var i,j,x,ii,jj,xx,k,sl:longint;
begin
     sd:=4;
     for i:=1 to m-1 do
         for j:=1 to n-1 do
         begin
              inc(sd);
              stt[i,j]:=sd;
         end;
     for i:=1 to m-1 do
     begin
          stt[i,0]:=1;
          stt[i,n]:=3;
     end;
     for j:=1 to n-1 do
     begin
          stt[0,j]:=4;
          stt[m,j]:=2;
     end;
     pos[1]:=1;
     for i:=1 to m-1 do
     begin
          x:=stt[i,1];
          a[i]:=x;
          c[i]:=ngang[i,1];
     end;
     pos[2]:=pos[1]+m-1;
     for j:=1 to n-1 do
     begin
          x:=stt[m-1,j];
          a[pos[2]+j-1]:=x;
          c[pos[2]+j-1]:=doc[m,j];
     end;
     pos[3]:=pos[2]+n-1;
     for i:=1 to m-1 do
     begin
          x:=stt[i,n-1];
          a[pos[3]+i-1]:=x;
          c[pos[3]+i-1]:=ngang[i,n];
     end;
     pos[4]:=pos[3]+m-1;
     for j:=1 to n-1 do
     begin
          x:=stt[1,j];
          a[pos[4]+j-1]:=x;
          c[pos[4]+j-1]:=doc[1,j];
     end;
     sl:=n-1;
     for i:=1 to m-1 do
         for j:=1 to n-1 do
         begin
              x:=stt[i,j];
              pos[x]:=pos[x-1]+sl;
              for k:=1 to 4 do
              begin
                   ii:=i+dx[k]; jj:=j+dy[k];
                   xx:=stt[ii,jj];
                   a[pos[x]+k-1]:=xx;
                   c[pos[x]+k-1]:=calc(i,j,ii,jj);
              end;
              sl:=4;
         end;
     pos[sd+1]:=pos[sd]+sl;
end;

procedure update(x:longint);
var cha,con:longint;
begin
     con:=p[x];
     if con=0 then
     begin
          inc(nh); con:=nh;
     end;
     cha:=con shr 1;
     while (cha>0) and (d[h[cha]]>d[x]) do
     begin
          h[con]:=h[cha];
          p[h[con]]:=con;
          con:=cha;
          cha:=con shr 1;
     end;
     h[con]:=x; p[x]:=con;
end;

function pop:longint;
var x,cha,con:longint;
begin
     pop:=h[1];
     x:=h[nh]; dec(nh);
     cha:=1; con:=2;
     while (con<=nh) do
     begin
          if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
          if d[h[con]]>=d[x] then break;
          h[cha]:=h[con];
          p[h[cha]]:=cha;
          cha:=con;
          con:=cha shl 1;
     end;
     h[cha]:=x; p[x]:=cha;
end;

procedure dijk(x:longint);
var i,j,y,t:longint;
begin
     for i:=1 to sd do
     begin
          free[i]:=true;
          d[i]:=oo;
     end;
     fillchar(p,sizeof(p),0);
     nh:=0;
     d[x]:=0; t:=x;
     update(x);
     repeat
           x:=pop; free[x]:=false;
           if (x<>t) and (x<5) then continue;
           for i:=pos[x] to pos[x+1]-1 do
           begin
                y:=a[i];
                if d[y]>d[x]+c[i] then
                begin
                     d[y]:=d[x]+c[i];
                     update(y);
                end;
           end;
     until (not free[3]) or (not free[4]);
     if d[3]<re then re:=d[3];
     if d[4]<re then re:=d[4];
end;

procedure pr;
begin
     oo:=oo*oo;
     re:=oo;
     dijk(1);
     dijk(2);
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     init;
     pr;
     close(input);
end.

Download