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.